数学の置換をプログラムで書くには？

質問

現在、C言語で置換を行うプログラムを書こうと思っています。

まずint型の要素数nの配列permutationを用意し、これを用いて、重複なく、不足なく、n!通り全ての置換を行うにはどのようにすればよいでしょうか？

プログラムの形式としては、配列permutationが宣言されている状態で、

for(int i = 0;i < factorial(n);i++){
//permutationを用いた計算（permutationの値は変化しない）

//ここでpermutationの値を置換する
}

という感じです(factorial(n)はnの階乗です)。

回答よろしくお願いします。

回答No.1

noname#196706 · ベストアンサー

http://en.cppreference.com/w/cpp/algorithm/next_permutation
このページのコードが参考になると思います。

お礼

ありがとうございます。

参考になりました。

回答No.2

επιστημη（@episteme）

#1 で紹介されてたコードをCに書き換えてみた。

#include <stdio.h>

typedef int ITEM;
typedef ITEM* Iterator;

// *x と *y を交換する
void iter_swap(Iterator x, Iterator y) {
ITEM t = *x;
*x = *y;
*y = t;
}

// first以上 last未満 の範囲を反転(逆順)する
void reverse(Iterator first, Iterator last) {
while ( first != last && first != --last ) {
iter_swap(first, last);
++first;
}
}

typedef int bool;
const int false = 0;
const int true = 1;

bool next_permutation(Iterator first, Iterator last) {
Iterator i = last;
if (first == last) return false;
if (first == --i) return false;

while (1) {
Iterator i1, i2;

i1 = i;
if (*--i < *i1) {
i2 = last;
while (!(*i < *--i2))
;
iter_swap(i, i2);
reverse(i1, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}

// おためし

int main() {
int i;
const int N = 4;
ITEM data[] = { 1, 2, 3, 4 };
do {
for ( i = 0; i < N; ++i ) {
printf("%d", data[i]);
}
printf("\n");
} while ( next_permutation(data, data+N) );
return 0;
}

お礼

ありがとうございます。

実はcions様の回答を参考に既にCで書き換えていましたが……ｗｗ