2016-04-30 12 views
1

入力文字列からすべての可能な順列を辞書順に出力する関数を作っています。一意の文字ではない辞書順での並べ替え

私は次のコードを持っている:

void permutations_print(char *permutations, int index, int length) { 
    if (index == length) { 
     printf("\"%s\"\n", permutations); 
    } 
    for (int i = index; i < length; i++) { 
     rotate(permutations, i, index); 
     permutations_to_array(permutations, index + 1, length); 
     rotate_back(permutations, index, i); 
    } 
} 

void rotate(char to_swap[], int i, int j) { 
    char temp = to_swap[i]; 
    for (int k = i; k > j; k--) { 
     to_swap[k] = to_swap[k - 1]; 
    } 
    to_swap[j] = temp; 
} 

void rotate_back(char to_swap[], int i, int j) { 
    char tmp = to_swap[i]; 
    for (int k = i; k < j; k++) { 
     to_swap[k] = to_swap[k + 1]; 
    } 
    to_swap[j] = tmp; 
} 

入力文字列の順列がソートされpermutations_printです。

ユニークな文字だけの並べ替えには問題ありませんが、文字以外の文字列や、アイデアの修正/修正の仕方も必要ですか?私は再帰を使用しなければならず、並べ替えを使用するべきではありません。そして、私はすべてを印刷したい、重複して印刷したい。

+0

文字列内の各文字の出現回数を示す配列から開始することができます(つまり、文字を配列のインデックスとして使用する)。それは正しい順序で順列を生成するのに役立ちます。 –

+0

更新:私はその戦略を使ってそれを行うことができました。 –

答えて

0

警告:Cプログラマではないので、私のコードを確実に改善することができます。

あなたはこのようなもので反復的にそれを行うことができます。

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 

void swap(char* array, int i, int j); 
void reverse(char* array, int left, int right); 
bool nextPermutation(char* array, int n); 
int compareCharacters(const void * a, const void * b); 
void printPermutations(char *permutations, int length); 

int main() { 
    char myArray[] = "hey"; 
    printPermutations(myArray, 3); 

    return 0; 
} 

void printPermutations(char *array, int length) { 
    qsort(array, length, sizeof(char), compareCharacters); 
    *(array + length) = '\0'; 

    do { 
     printf("%s\n", array); 
    } while (nextPermutation(array, length)); 
} 

int compareCharacters(const void * a, const void * b) { 
    return (*(char*)a - *(char*)b); 
} 

bool nextPermutation(char* array, int n) { 
    if (n <= 1) { 
     return false; 
    } 

    // Find index, swapIndex1, of rightmost number that has a number greater than it 
    int swapIndex1; 

    for (swapIndex1 = n - 2; swapIndex1 >= 0; --swapIndex1) { 
     if (array[swapIndex1] < array[swapIndex1 + 1]) { 
      break; 
     } 
    } 

    if (swapIndex1 == -1) { 
     return false; 
    } 

    // Find index, swapIndex2, of smallest number to the right of that and greater than it 
    int swapIndex2 = swapIndex1 + 1; 
    int minToRight = array[swapIndex2]; 

    for (int i = swapIndex2 + 1; i < n; ++i) { 
     if (array[i] <= minToRight && array[i] > array[swapIndex1]) { 
      minToRight = array[i]; 
      swapIndex2 = i; 
     } 
    } 

    // Swap values at swapIndex1 and swapIndex2 
    swap(array, swapIndex1, swapIndex2); 

    // Reverse values from swapIndex1+1 to n-1 
    reverse(array, swapIndex1 + 1, n - 1); 

    return true; 
} 

void swap(char* array, int i, int j) { 
    char temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 

void reverse(char* array, int left, int right) { 
    for (; left < right; ++left, --right) { 
     swap(array, left, right); 
    } 
} 

アルゴリズムはhereに記載されています。例/説明については、コメントのセクションをご覧ください。以下の転記をご覧ください。

次に1-9から順番に番号を並べるふりをしてみましょう。例えば、我々が持っていると仮定し

を:123479865

を私たちは、これが何を意味するのか123479865.

の数字を並べ替えることによって得ることができる123479865より大きい最小の番号を見つけたいのは、私たちが作る必要があるということです現在の数字より少なくとも1桁大きい私たちの選択肢があれば、一番右の数字を大きくしたいのですが、それは最小の変化をもたらすからです。左の数字を大きくすると、価値の変化が大きくなります。

例:12347986 => 12347986 。したがって、我々はその右端の桁を見つけたい 23479865 => 23479865.

よりもはるかに小さい変化であり、私たちはもっと大きくすることができます。数字を大きくするためには、シーケンス内で別の数字を見つけて、それを入れ替えなければなりません。

注:数値を左(たとえば6)にスワップすることはできません。なぜなら、数字を左に減らすことになり、全体の数値を小さくするからです。たとえば、5と6を6と交換すると、1234798 となり、1234798 より小さくなります。したがって、私たちは常に右の数字にスワップします。

だから、右端の数字から始まる123479865まで進んでみましょう。

5の右には何もありませんので、5を大きくすることはできません。

ここで、6を考えてみましょう.6の右側には6より大きい何もありません。したがって、6を大きくすることはできません。

ここで8を考えてみましょう.8の右側には8より大きい何もありません。したがって、8を大きくすることはできません。

ここで9を考えてみましょう.9の右側には9より大きい何もないので、9を大きくすることはできません。

ここでは7を考えてみましょう.7の右側には、7と9と8の数字がいくつかあります。したがって、7を大きくすることができます。言い換えれば、7を8に交換する必要があります。つまり、1234 65 。

番号123489765は123479865よりも大きいですが、それは我々が今、次の数字のいずれかを変更するには無限の自由を持っているので、我々はこれを行うことができます123479865.よりも大きいということ維持しながら、我々は実際にそれを小さくすることができます:12348 (8の右にあるもの)。これらの数字は、できるだけ小さくすることができます。なぜなら、左にある8は、新しい数字が常に大きくなることを保証するからです。

数字9765を小さくする最も良い方法は、数字を大きく並べ替えて5679を与えることです。並べ替えは、左端の値が全体の値に最も寄与するために機能します。したがって、最も左の桁を最小の桁にします。私たちの答えである、12348 で私たちを残し

注:実際には、8の右側の数字をソートする必要はありません。右側から8までの数字が増加する順番であることがわかっているので、私たちは以前の数字よりも小さい数字になった)。

関連する問題