-1

この問題をオンラインで見たので、 で解決しようとしていましたC++。私は次のアルゴリズムを持っています:

char permutations( const char* word ){

  int size = strlen( word );
  if( size <= 1 ){
      return word;
  }
  else{
    string output = word[ 0 ];
    for( int i = 0; i < size; i++ ){
        output += permutations( word );
        cout << output << endl;
        output = word[ i ];
     }
  }
  return "";
}

たとえば、入力として, , , ,をabc表示したい場合。だから、私がやろうとしていることはabcacbbacbcacabcba

'abc' => 'a' + 'bc' => 'a' + 'b' + 'c'
                    => 'a' + 'c' + 'b'

wordそのため、関数呼び出しごとに少ない文字を渡す必要があります。誰かがそれを行う方法を手伝ってもらえますか?

4

2 に答える 2

5

algorithmC++のヘッダー ライブラリを使用することをお勧めします。はるかに簡単です。そして、関数として次のように書くことができます:

void anagram(string input){
    sort(input.begin(), input.end());
    do
        cout << input << endl;
    while(next_permutation(input.begin(), input.end()));
}

ただし、STL なしで必要な場合は、次のようにすることができます。

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

void swap (char *x, char *y)
{
    char ch = *x;
    *x = *y;
    *y = ch;
};

void permutate_(char* str, size_t index )
{
    size_t i = 0;
    size_t slen = strlen(str);
    char lastChar = 0;

    if (index == slen )
    {
        puts(str);
        return;
    }

    for (i = index; i < slen; i++ )
    {
        if (lastChar == str[i])
            continue;
        else
            lastChar = str[i];

        swap(str+index, str+i);
        permutate_(str, index + 1);
        swap(str+index, str+i);
    }
}

// pretty lame, but effective, comparitor for determining winner
static int cmpch(const void * a, const void * b)
{
    return ( *(char*)a - *(char*)b );
}

// loader for real permutor
void permutate(char* str)
{
    qsort(str, strlen(str), sizeof(str[0]), cmpch);
    permutate_(str, 0);
}

ソートされた文字の配列を送信することで呼び出すことができます。

permutate("Hello World");

非 STL アプローチはhere から得られました。

于 2012-09-29T23:00:43.027 に答える
0

STL はすばらしい:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void permutations(const char *word) {
    string s = word;
    sort(s.begin(), s.end());
    cout << s << endl;
    while(next_permutation(s.begin(), s.end()))
        cout << s << endl;
}

int main() {
    permutations("abc");
    return 0;
}

これで、next_permutation非常に簡単に実装できます。x文字列の末尾から、次の要素より小さい要素が見つかるまで逆方向に繰り返します。x文字列の残りの部分よりも大きい次の値と交換し、xその後の要素を逆にします。だから、以来にabcdなります; sinceとなり、 ;の最後の 3 文字を裏返します。になりますので交換いたします。abdcc < dcdbadabcc < ddcbabdcacabdb < dbc

于 2012-09-29T23:00:15.357 に答える