c# - 为一组字符生成所有可能的模式

Question

可能的重复：
生成所有可能的组合

我想为一个字符串生成所有可能的唯一模式，该模式将包括其所有字符，包括重复字符（如果有）。

例如：

字符串：abc
模式：abc acb bca bac cab cba

字符串：abb
模式：abb bab bba

此外，是否有一个公式可以说明可以为字符串创建多少个唯一模式来验证算法的有效性？到目前为止，我尝试了多种方法，但随着字符数量的增加，结果并不可靠。

Answer 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);
              }
       }
  }

Answer 2

如果您从数据排序开始，您可以使用重复调用 std::next_permutation 来循环遍历所有排列。std::next_permutation 处理重复元素的情况，比如你的 abb 字符串，没有问题。

Answer 3

我的想法与 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();

}

检查此链接以确定可以创建多少个独特的模式！希望能帮助到你！

Answer 4

要计算唯一排列，它只是单词的长度（例如 3）到可能字符的幂。因此，如果都是小写字符并且单词长度为 3，则它是 3^26=2541865828329（26，因为这是英文字母表中小写字符的数量）组合。

您可以使用递归计算所有可能的组合。