是否有非递归解决方案来获取字符串数组的所有可能串联的列表?

Question

我接收一个字符串数组作为输入。
我必须创建一个字符串列表，这些字符串是输入数组所有字符串的串联，每个字符串出现一次，并且只出现一次。
例如，如果输入数组是["aa","bb","cc"]则生成的字符串列表将"aabbcc",aaccbb","bbaacc","bbccaa",ccaabb","ccbbaa"
输入数组的长度未知，它可以是任何数字。
数组中所有子字符串的长度相同。
我看到这个Java：获取List>问题的所有连接。
但是有没有非递归的解决方案呢？

Answer 1

我刚刚写了一个对整数做同样的事情的例子： 获取任意数量元素的所有组合

您可以简单地通过String[]替换int[]。

一个完整的交互式示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
class Main
{
/**
* Return all possible combination of n Strings
* @param n Number of parts to combine in each row
* @param set Array of Strings to combine
*/
static List<String[]> getAll(int n, String[] set)
{
List<String[]> combinations = new ArrayList<>();
// First step (0)
// Create initial combinations, filled with the first String.
for (int number = 0; number < set.length; number++)
{
String[] array = new String[n]; // the final size of each array is already known
array[0] = set[number]; // fill the first Part
combinations.add(array);
}
// In each following step, we add one number to each combination
for (int step = 1; step < n; step++)
{
// Backup the size because we do not want to process
// the new items that are added by the following loop itself.
int size = combinations.size();
// Add one number to the existing combinations
for (int combination = 0; combination < size; combination++)
{
// Add one part to the existing array
String[] array = combinations.get(combination);
array[step] = set[0];
// For all additional Strings, create a copy of the array
for (int number = 1; number < set.length; number++)
{
String[] copy = Arrays.copyOf(array, array.length);
copy[step] = set[number];
combinations.add(copy);
}
}
}
return combinations;
}
public static void main(String[] args)
{
System.out.println("Enter some Strings, delimited by space");
Scanner in=new Scanner(System.in);
String line=in.nextLine();
String[] set=line.split("\s+");
// Calculate all possible combinations
List<String[]> combinations = getAll(set.length, set);
// Print the result
for (String[] combination : combinations)
{
System.out.println(Arrays.toString(combination));
}
}
}

输出：

Enter some Strings, delimited by space
aa bb cc
[aa, aa, aa]
[bb, aa, aa]
[cc, aa, aa]
[aa, bb, aa]
[aa, cc, aa]
[bb, bb, aa]
[bb, cc, aa]
[cc, bb, aa]
[cc, cc, aa]
[aa, aa, bb]
[aa, aa, cc]
[bb, aa, bb]
[bb, aa, cc]
[cc, aa, bb]
[cc, aa, cc]
[aa, bb, bb]
[aa, bb, cc]
[aa, cc, bb]
[aa, cc, cc]
[bb, bb, bb]
[bb, bb, cc]
[bb, cc, bb]
[bb, cc, cc]
[cc, bb, bb]
[cc, bb, cc]
[cc, cc, bb]
[cc, cc, cc]

要更改输出格式，您可以使用：

// Print the result
for (String[] combination : combinations)
{
String s=String.join("",combination); // Concatenate the parts of each combination
System.out.println(s);
}

输出格式为：

aaaaaa
bbaaaa
ccaaaa
aabbaa
...

请查看链接的主题以找到其工作原理的说明。