生成字符串所有组合的算法

Question

我在网上找到了一个链接，该链接展示了一种生成字符串所有组合的算法：http://www.mytechinterviews.com/combinations-of-a-string

以下是复制的算法。

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
} 

combine("abc", new StringBuffer(), 0);

我不理解的是这行代码：

outstr.deleteCharAt(outstr.length() - 1);

如果我删除这一行，程序显然就不再工作了，但是为什么一开始需要它呢？我理解递归的思想，我们改变一个初始字符并在其余字符上进行递归，但是deleteChar这一行似乎在逻辑上没有任何地方可以放置。添加outstr.deleteCharAt行的原因是什么？

- john

---

由于我们想要所有的组合，包括charAt(i)和不包括charAt(i)，因此我们需要将这两种情况分开处理。那些不包含charAt(i)的组合在下一次for循环迭代中会被deleteCharAt()函数神奇地处理掉，在当前迭代结束之前。 - Hackless

Answer 1

计算字符串可能组合的最简单方法如下...

在数学上，找到给定N个中的R组合 = NcR

因此，我们要找的是，所有可能的组合= Nc0 + Nc1 .... + Ncn = 2 Pow N

因此，对于长度为N个字符的给定单词，您将获得2 Pow N种组合。

如果您用二进制表示1到（2 Pow N）的整数，并将您的字符放置在存在1的地方，最终您将得到解决方案。

示例：

输入：ABC

解法：

ABC的长度为3。因此，可能的组合2 Pow 3 = 8

如果用二进制表示0 - 8

000 =

001 = C

010 = B

011 = BC

100 = A

101 = AC

110 = AB

111 = ABC

以上显示了所有可能的组合。

- Sunil

---

谢谢！这使得理解解决方案更容易了。 - asgs

太棒了！我相信这是最直观的实现方式。 - Vikrant Goel

它没有BA、CA、CBA等等，我猜这些可能是不同的字符串。 - Vikash

@Vikash，BA是AB，CA是AC，而CBA是ABC，因为这是组合而不是排列。 - Cloud Cho

Answer 2

outstr.deleteCharAt 的调用通过删除 outstr 的最后一个字符来抵消 outstr.append 的效果。

每个循环迭代都按照以下步骤执行：

1. 追加一个字符
2. 打印结果
3. 在级别为 i+1 的层次上执行递归调用
4. 删除我们在第一步添加的字符

- Sergey Kalinichenko

Answer 3

它平衡循环体的第一行，通过从instr中删除附加的字符，将outstr恢复为循环体顶部的状态。

- Scott Hunter

Answer 4

我们可以使用之前提到的位运算概念来生成一个字符串的所有子串。以下是用C++编写的代码（但你可以理解）：-

string s;
int n = s.size();
int num = 1<<n;
for(int i =1; i< num ; i++){ //Checks all the permutations.
    int value = i;
    int j, pos;
    for (j=1, pos=1; j < num; j<<=1, pos++) //Finds the bits that are set
        if (i & j)
            cout<<s[pos-1]; //You can print s[n-pos] to print according to bit position
    cout<<endl;        
}

Eg;- String s = abc ,

 The size is 3  . So we check from 1 to 7 ( 1<<3).
 for i = 1 ( 001 ) , the first bit is set, so a is printed.
 for i = 2 ( 010 ) , the second bit is set, so b is printed.
 for i = 3 ( 011 ) , the first and second bit are set, so ab is printed.
 .
 .
 .
 for i = 7 ( 111 ) , all three bits are set, so abc is printed.

- user2125722

Answer 5

这里是没有 OP 问题中棘手的回溯步骤的 C++ 代码。

#include <iostream>
#include <string>
using namespace std;
static const string in("abc");
void combine(int i, string out) // each out is a combo of letters up to ith
{
    if (i==in.size()) { // all letters have been looked at
        cout << out << endl;
        return;
    }
    combine(i+1, out);  // showing the ith letter in final out
    combine(i+1, out+in[i]); // skipping the ith letter in final out
}

int main()
{
    combine(0, "");
    return 0;
}

我希望这样能更好地表达组合的精神。

- Hackless

---

你能添加解释吗？ - Cloud Cho

@Cloud-Cho，你认为添加的注释有意义吗？ - Hackless

谢谢您的评论，它很有帮助。我运行了您的代码，它从最后一个字母“c”开始打印，这很有趣。您能分享一下您是如何想出这个算法（或参考资料）的吗？ - Cloud Cho

我不记得这个想法的确切来源。它可能来自于那些面试准备书籍之一，也可能不是。感谢您实际编译代码并检查结果！ - Hackless

Answer 6

这个算法非常符合逻辑。我们这里使用了一个递归算法。在每个位置i，我们放置一个字符串的字母，然后递归调用函数，在下一个位置放置另一个字母。但是，当我们从递归返回时，我们需要删除最初放置的字符，以便我们可以用序列中的下一个可能字符替换它。例如：

append a on pos 0 -> a
call recursion
append a on pos 1 -> aa
call recursion
append a on pos 2 -> aaa
return from recursion
remove a from pos 2 -> aa
append b on pos 2 -> aab
return from recursion
remove b from pos 2 -> aa
append c on pos 2 -> aac
etc.

- Tudor

Answer 7

下面的代码是用来生成字符串的排列和组合的，基本上的概念是一次选择一个字符：

public class permutecombo
{
  static void initiate(String s)
  {
    permute("", s);
    System.out.println("----------------------------------------- ");
    combo("", s);
    System.out.println("----------------------------------------- ");
  }

  static void combo(String prefix, String s)
  {
    int N = s.length();

    System.out.println(prefix);

    for (int i = 0 ; i < N ; i++)
      combo(prefix + s.charAt(i), s.substring(i+1));
  }
  static void permute(String prefix, String s)
  {
    int N = s.length();

    if (N == 0)
      System.out.println(" " + prefix);

    for (int i = 0 ; i < N ; i++)
      permute(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
  }

  public static void main(String[] args)
  {
    String s = "1234";
    initiate(s);
  }
}

- nmd

Answer 8

outstr.deleteCharAt(outstr.length() - 1); 

这意味着你有

n^(n-1)/2 pairs of combinations.

迭代的for循环在递归函数调用后不会停止，因此您需要删除输出缓冲区中的最后一个字符，因为您不想得到

。

n^n/2 pairs of combinations.

在图论中，这将是一个短路。

- Micromega

Answer 9

// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

import java.util.*;
public class Permutation {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("ENTER A STRING");
        Set<String> se=find(in.nextLine());
        System.out.println((se));
    }
    public static Set<String> find(String s)
    {
        Set<String> ss=new HashSet<String>();
        if(s==null)
        {
            return null;
        }
        if(s.length()==0)
        {
            ss.add("");
        }
        else
        {
            char c=s.charAt(0);
            String st=s.substring(1);
            Set<String> qq=find(st);
            for(String str:qq)
            {
                for(int i=0;i<=str.length();i++)
                {
                    ss.add(comb(str,c,i));
                }
            }
        }
        return ss;

    }
    public static String comb(String s,char c,int i)
    {
        String start=s.substring(0,i);
        String end=s.substring(i);
        return start+c+end;
    }

}


// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

- Rathina Moorthy Nataraj

Answer 10

我认为代码中的outstr.deleteCharAt(outstr.length() - 1)是回溯法。

这里有一个来自John Mongan的书第7章的好例子：

给定示例中的字符串：wxyz
   现在John展示了他如何从字符串中得出所有组合：
   （请记住，当您到达字符串末尾时，您需要返回。在此示例中，这是字母'z'。）

   ---->
   w wx wxy wxyz
   wxz <- wxyz - wxy - wx：删除z和y（1）
   wy <- wxz - wx - w：删除z和x（2） wyz
   wz <- wyz - wy - w：删除z和y（3）

   x <- wz - w - ' '：删除z和w（4） xy xyz
   xz <- wyz - xy - x：删除z和y（5）

y <- xz - x - ' ': 移除 z 和 x (6) yz

z < yz - y - ' ': 移除 y 和 z (7)

步骤（1）〜（7）是回溯，可以通过 outstr.deleteCharAt(outstr.length() - 1) 实现。

---

为更好地理解，这里是约翰从这本书中直接摘录的伪代码：

对于输入开始位置到输入字符串结尾的每个字母
    选择将字母置于输出字符串的当前位置
    打印输出字符串中的字母
    如果当前字母不是输入字符串中的最后一个
在下一个位置生成剩余组合，迭代从刚选定的字母之后的下一个字母开始

最后一行以“生成”开头是回溯。

- Cloud Cho