3

可能重复：
生成给定字符串的所有排列

给定一个长度n=4, 和 a set of characters -> {'a', 'b'}，如何编写一些 java 代码来生成包含集合中字符的长度为 n 的所有可能字符串？

对于上面的示例，结果应该有 2^4=16 个字符串，即：

aaaa
aaab
aabb
abbb
baaa
baab
babb
bbbb
bbaa
bbab
bbba
abaa
abab
abba
baba
aaba

这是我的代码片段：

public void process(String result, String string)
{
    if(string.length() == 0)
    {
        System.out.println(result);
    }else{
        for(int i = 0; i < string.length(); i++)
        {
            String newResult = new String(result+string.charAt(i));
            String newString = new String(string.substring(0,i) + string.substring(i+1, string.length()));
            process(newResult, newString);
        }
    }
}

这似乎只是做排列，而不是我想要的......提前谢谢你:)

4

3 回答 3

7

以与计算相同的方式思考它。从技术上讲，您从 aaaa 到 bbbb “计数”，就像二进制一样。

aaaa -> 0000
aaab -> 0001
aaba -> 0010
aabb -> 0011
...
bbbb -> 1111

在没有看到您尝试过的内容的情况下，我无法为您提供更多帮助，但基本上您需要通过计数来枚举“最低”元素和“最高”元素之间的所有“数字”。

对于更高的元素计数，只需将您的计数视为在更高的基数中计数。对于八个元素，Set = {a, b, c, d, e, f, g, h}，你会在本质上是八进制数：

aaaa -> 0000
aaab -> 0001
...
aaah -> 0007
aaba -> 0010
...
hhhh -> 7777

这与您通过从 0000 计数到 9999 来枚举长度为 4 的 0-9 的所有组合的方式相同。

编辑：

感谢您发布您的代码。你是对的，你正在做排列。更好的方法是使用这里讨论的多重组合（与 ordererd 组合集中的重复元素组合）算法。

于 2012-09-05T20:02:04.280 回答
0

这可能很容易出错，因为我没有测试过，但它应该可以工作。即使没有，它也应该非常接近您正在寻找的内容。请注意，第一个 for 循环会填充 resultList 而不是设置值，因为不会有任何内容可附加。

让我知道是否有问题，我会纠正它。

ArrayList<String> results = new ArrayList<String>();
ArrayList<String> components = new ArrayList<String>(){"a","b","c"};
int n = 4;

int size = components.size();
for ( int j = 0; j < size; j++ )
{
  // start with size^(n-1) copies of each letter. 
  for ( int i = 0; i < Math.pow( size, n-1); i++ )
  {
    results.add( components.get( j ) );
  }
}

// At this point you have each letter in there once...

for( int depth = 1; depth < n; depth++ )
{
  for( int j = 0; j < size; j++ )
  {
    String toAppend = components.get( j );
    for( int i = j; i < results.size(); i += size )
    {
      String current = results.get( i );
      current += toAppend;
      results.set( i, current );
    }
  }
}
于 2012-09-05T20:45:09.637 回答
0

您已经得到了答案，但我觉得您需要更多帮助：

if(string.length() == 0)
{
System.out.println(result);
}

为什么要打印一个空字符串？它根本不会打印任何内容。您可能想要打印一条消息并退出您的功能。

于 2012-09-05T20:55:28.617 回答