0

C で基本的な順列プログラムを作成しました。ユーザーが数値を入力すると、その数値のすべての順列が出力されます。

基本的には、これがどのように機能するかです (主なアルゴリズムは、次に高い順列を見つけるために使用されるものです):

int currentPerm = toAscending(num);
int lastPerm = toDescending(num);
int counter = 1;

printf("%d", currentPerm);

while (currentPerm != lastPerm)
{
   counter++;
   currentPerm = nextHigherPerm(currentPerm);
   printf("%d", currentPerm);
}

ただし、数値入力に重複する数字が含まれている場合 (重複)、一部の順列は重複しているため生成されません。カウンターは想定とは異なる数値を示します - 数値の桁数の階乗を表示する代わりに、一意の順列のみの小さい数値を示します。

例えば：

num = 1234567
counter = 5040 (!7 - all unique)

num = 1123456
counter = 2520

num = 1112345
counter = 840

繰り返し/重複した数字を異なるものとして扱いたい-一意の順列だけを生成したくない-むしろ、それらが繰り返されているかどうかに関係なく、すべての順列を生成します。

4

4 に答える 4

1

繰り返される/重複する数字を異なるものとして扱いたいのですが、一意の順列の数だけを計算したくありません。

使用する情報がnextHigherPerm()渡された番号だけである場合は、運が悪いです。考えてみてくださいnextHigherPerm(122)。122関数は、すでにいくつのバージョンが表示されているかをどのように知ることができますか？nextHigherPerm(122)戻る必要があります122か？212ジェネレータの現在の状態を個別に追跡しない限り、知る方法はありません。

于 2012-11-12T21:03:38.597 に答える
1

ABC のように 3 文字の場合ABC, ACB, BAC, BCA, CAB, CBA、 、6 つの組み合わせ (6!) を作成できます。これらの文字のうち 2 つが AAB のように繰り返される場合、AAB、ABA、BAA、IT は 3 ではありません。だからそれは何ですか？それはどこから来るのですか？数字または文字が繰り返されるときにそれを計算する実際の方法は、組み合わせを使用することです->( n k ) = n! / ( n! * ( n! - k! ) )

別の例を挙げてみましょAAABうAAAB, AABA, ABAA, BAAA:4C3 = 4.

これらすべてのリストを生成する正しい手順は次のとおりです。

  • 数字を配列に格納します。例ABCD。
  • 配列の 0 要素をピボット要素として設定し、temp 配列から除外します。A {BCD}
  • 次に、すべての組み合わせ (繰り返しも含む) が必要な場合は、 n 要素に到達するまで、時間配列の要素を右または左に (好きなように) 移動します。

A{BCD}------------A{CDB}------------A{DBC}

  • 2 番目のステップをもう一度実行しますが、temp 配列を使用します。

A{B{CD}}------------A{C{DB}}------------A{D{BC}}

  • 3 番目の手順をもう一度実行しますが、2 番目の一時配列内で行います。

A{B{CD}}------------A{C{DB}}------------A{D{BC}}

A{B{DC}}------------A{C{BD}}------------A{D{CB}}

  • 最初の配列に移動し、配列 を移動し、BCDAB をピボットとして設定し、すべての組み合わせが見つかるまでこれを行います。
于 2012-11-12T21:56:15.073 に答える
1

ええと...入力文字列の長さの階乗を計算してみませんか? ;)

于 2012-11-12T20:52:07.877 に答える
0

それを文字列に変換してから、プログラムをアナグラムジェネレーターのように扱ってみませんか?

于 2012-11-12T21:08:25.670 に答える