java - 如何将所有数组排列迭代地返回到二维数组中?
问题描述
我正在尝试编写一个程序,它将遍历字符串数组的所有可能排列,并返回一个包含所有排列的二维数组。具体来说,我正在尝试使用长度为 4 的 String 数组来返回具有 24 行和 4 列的二维数组。
我只找到了迭代打印字符串但没有在数组中使用它们的方法。我也找到了递归方法,但是它们不起作用,因为我正在与其他人一起使用此代码,并且递归函数要困难得多。
对于我想要代码执行的操作,我知道标题应该是:
public class Permutation
{
public String[][] arrayPermutation(String[] str)
{
//code to return 2D array
}
}
//我尝试使用带有堆算法的递归方法,但它的参数非常//复杂。
我对编程很陌生,任何帮助将不胜感激。
解决方案
您的排列问题基本上只是一个索引排列问题。如果您可以在所有可能的变化中对从 0 到 n - 1 的数字进行排序,则可以将它们用作输入数组的索引,并简单地复制字符串。下面的算法不是最优的,但它足够图形化,可以迭代地解释和实现。
public static String[][] getAllPermutations(String[] str) {
LinkedList<Integer> current = new LinkedList<>();
LinkedList<Integer[]> permutations = new LinkedList<>();
int length = str.length;
current.add(-1);
while (!current.isEmpty()) {
// increment from the last position.
int position = Integer.MAX_VALUE;
position = getNextUnused(current, current.pop() + 1);
while (position >= length && !current.isEmpty()) {
position = getNextUnused(current, current.pop() + 1);
}
if (position < length) {
current.push(position);
} else {
break;
}
// fill with all available indexes.
while (current.size() < length) {
// find first unused index.
int unused = getNextUnused(current, 0);
current.push(unused);
}
// record result row.
permutations.add(current.toArray(new Integer[0]));
}
// select the right String, based on the index-permutation done before.
int numPermutations = permutations.size();
String[][] result = new String[numPermutations][length];
for (int i = 0; i < numPermutations; ++i) {
Integer[] indexes = permutations.get(i);
String[] row = new String[length];
for (int d = 0; d < length; ++d) {
row[d] = str[indexes[d]];
}
result[i] = row;
}
return result;
}
public static int getNextUnused(LinkedList<Integer> used, Integer current) {
int unused = current != null ? current : 0;
while (used.contains(unused)) {
++unused;
}
return unused;
}
getAllPermutations 方法被组织在一个初始化部分、一个收集所有排列(数字)的循环中,最后将找到的索引排列转换为字符串排列。
由于从 int 到 String 的转换是微不足道的,我将只解释集合部分。只要表示没有完全耗尽或从内部终止,循环就会迭代。
首先,我们增加表示 ( current
)。为此,我们取最后一个“数字”并将其增加到下一个自由值。然后我们弹出,如果我们超过长度,并查看下一个数字(并增加它)。我们继续这个,直到我们达到一个合法的值(一个低于长度)。
之后,我们用所有剩余的数字填充剩余的数字。完成后,我们将当前表示存储到数组列表中。
该算法在运行时不是最优的!堆更快。但是迭代地实现堆需要一个非平凡的堆栈,实现/解释起来很烦人。
推荐阅读
- file - 在目录中查找重复文件
- excel - 使用 VBA 查找和替换连续单元格中的值
- c - 在 FINTEK F81866A 芯片组上编程 GPIO 引脚
- hadoop - Hadoop权威指南的面向列的格式章节中的序列顺序?
- ruby - 自定义 Ruby on rails 验证错误
- kubernetes - Unabel 使用 openstack-helm 图表在 kubernetes 上部署 mariadb
- javascript - Marvel API 和 Insomnia(或 Postman):如何传递所需的哈希值?
- node.js - 你如何使用 distinct 和 mockingoose?
- python - 检查我的观点是否在我的屏幕的一部分
- c++ - 如何使用 break 停止循环?