1

重複の可能性: 考えられる
すべての組み合わせの生成

重複する文字を含むすべての文字を含む文字列に対して、可能なすべての一意のパターンを生成したいと考えています。

例えば：

文字列:abc
パターン:abc acb bca bac cab cba

文字列:abb
パターン:abb bab bba

また、アルゴリズムの有効性を検証するために、文字列からいくつの一意のパターンを作成できるかを示す式はありますか? これまでに複数のアプローチを試みましたが、文字数が増えるにつれて信頼できないことが判明しました。

4

4 に答える 4

1

次のようなことを試すことができます：-

  using System;

  namespace ConsoleApplication3
 {
    class Permute
    {
             private void swap (ref char a, ref char b)
             {
                    if(a==b)return;
                    a^=b;
                    b^=a;
                    a^=b;
              }

              public void setper(char[] list)
              {
                    int x=list.Length-1;
                    go(list,0,x);
              }

              private void go (char[] list, int k, int m)
              {
                    int i;
                    if (k == m)
                       {
                             Console.Write (list);
                             Console.WriteLine (" ");
                        }
                    else
                         for (i = k; i <= m; i++)
                        {
                               swap (ref list[k],ref list[i]);
                               go (list, k+1, m);
                               swap (ref list[k],ref list[i]);
                        }
               }
     }

     class Class1
    {
           static void Main()
           {

                  Permute p = new Permute();
                  string c="sagiv";
                   char []c2=c.ToCharArray ();
                   /*calling the permute*/
                  p.setper(c2);
              }
       }
  }
于 2012-11-27T15:31:27.143 に答える
0

私のアイデアは Rahul Tripathi のアイデアと似ていますが、重複した要素に対して適切に機能するようにするためにトリッキーなことをしました。スワップ操作を行う前にはいつでも、この要素が以前に表示されたかどうかを確認するために振り返ります。要素が重複している場合は、スワップ操作を行うべきではありません。コードは以下の C++ を使用したものです。

#include<iostream>

using namespace std;

bool isDupilicate(char input[],int start,int j)
{
     bool ret=false;
     for(int i=start;i<j;++i)
     {
             if(input[i]==input[j])
             {
                ret=true;
                break;
             }
     }
     return ret;
}

void swap(char& a,char &b)
{
     char temp=a;
     a=b;
     b=temp;
}

void permutation(char input[],int start,int length)
{
       if(start==length)
       {
           for(int i=0;i<length;++i)cout<<input[i];
           cout<<endl;
       }
       else 
       {
           for(int i=start;i<length;++i)
           {
                   if(isDupilicate(input,start,i))continue;
                   swap(input[i],input[start]);
                   permutation(input,start+1,length);
                   swap(input[i],input[start]);

           } 
       }          
}

int main()
{
    cout<<"Input for abb"<<endl;
    char input[3]={'a','b','b'};
    permutation(input,0,3);
    cout<<"________________"<<endl;

    cout<<"Input for abc"<<endl;
    input[2]='c';
    permutation(input,0,3);

    getchar();
    getchar();

}

このリンクをチェックして、作成できるユニークなパターンの数を確認してください! それが役に立てば幸い！

于 2012-11-27T17:01:05.667 に答える
0

データを並べ替えた状態で開始する場合は、std::next_permutation を繰り返し呼び出して、すべての順列を循環させることができます。std::next_permutation は、abb 文字列のように要素が繰り返されるケースを問題なく処理します。

于 2012-11-27T16:04:30.300 に答える
-2

一意の順列を計算するには、単語の長さ（たとえば、3）を可能な文字の累乗で計算します。したがって、すべて小文字で、単語の長さが3の場合、3 ^ 26 = 2541865828329（英語のアルファベットの小文字の数であるため26）の組み合わせになります。

再帰を使用して、考えられるすべての組み合わせを計算できます。

于 2012-11-27T15:38:51.617 に答える