みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

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

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

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

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

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

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

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

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

投稿日時 - 2013-07-21 01:46:28

QNo.8185005

すぐに回答ほしいです

質問者が選んだベストアンサー

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

投稿日時 - 2013-07-21 07:21:13

お礼

ありがとうございます。

参考になりました。

投稿日時 - 2013-07-22 00:25:12

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.2

#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;
}

投稿日時 - 2013-07-21 21:42:02

お礼

ありがとうございます。

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

投稿日時 - 2013-07-22 00:25:08

あなたにオススメの質問