生成 Java 中多个列表的所有排列
Generate all permutations of several lists in Java
我有 n
个列表,例如:
L_1 = [a_11, a_12, ...]
L_2 = [a_21, a_22, ...]
...
L_n = [a_n1, a_n2, ...]
其中第 i
个列表有 k_i
个元素。
现在,我想生成所有 n
元素列表,其中 i
th 元素来自 L_i
,我的意思是:
[a_11, a_21, ..., a_n1]
[a_11, a_21, ..., a_n2]
...
[a_11, a_22, ..., a_n1]
[a_11, a_22, ..., a_n2]
...
[a_12, a_21, ..., a_n1]
[a_12, a_21, ..., a_n2]
...
[a_12, a_22, ..., a_n1]
[a_12, a_22, ..., a_n2]
...
列表总数应等于k_1*k_2*...k_n
。您能否描述该算法的伪代码或使用 Java 代码?当列表数量被硬编码时,我可以使用嵌套的 for 循环来做到这一点,但是当 n
在运行时可自定义时,我完全被阻止了。
好的,我实现了这个算法。
import com.google.common.collect.Lists;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class PermutationGenerator {
private List<List<Integer>> result;
private List<List<Integer>> data;
public List<List<Integer>> permutate(List<List<Integer>> data) {
this.data = data;
this.result = Lists.newArrayList();
List<Integer> integers = new ArrayList<Integer>(Collections.nCopies(data.size(), 0));
foo(0, data.size() - 1, integers);
return result;
}
private void foo(Integer index, Integer maxIndex, List<Integer> output) {
List<Integer> list = data.get(index);
for (int i = 0; i < list.size(); i++) {
output.set(index, list.get(i));
if (index == maxIndex) {
result.add(Lists.newArrayList(output));
} else {
foo(index + 1, maxIndex, output);
}
}
}
}
测试class:
import com.google.common.collect.Lists;
import org.junit.Test;
import java.util.Arrays;
import java.util.List;
public class PermutationGeneratorTest {
@Test
public void test() throws Exception {
// given
PermutationGenerator pg = new PermutationGenerator();
List<Integer> list1 = Lists.newArrayList(1, 2, 3);
List<Integer> list2 = Lists.newArrayList(4, 5);
List<Integer> list3 = Lists.newArrayList(6, 7, 8, 9);
List<List<Integer>> input = Lists.newArrayList(list1, list2, list3);
// when
List<List<Integer>> output = pg.permutate(input);
// then
print(output);
}
private void print(List<List<Integer>> output) {
for (List<Integer> list : output) {
System.out.println(Arrays.toString(list.toArray()));
}
System.out.println("TOTAL: " + output.size());
}
}
输出:
[1, 4, 6]
[1, 4, 7]
[1, 4, 8]
[1, 4, 9]
[1, 5, 6]
[1, 5, 7]
[1, 5, 8]
[1, 5, 9]
[2, 4, 6]
[2, 4, 7]
[2, 4, 8]
[2, 4, 9]
[2, 5, 6]
[2, 5, 7]
[2, 5, 8]
[2, 5, 9]
[3, 4, 6]
[3, 4, 7]
[3, 4, 8]
[3, 4, 9]
[3, 5, 6]
[3, 5, 7]
[3, 5, 8]
[3, 5, 9]
TOTAL: 24
正如您自己发现的那样,通常的 技巧是将列表视为 g-adic 数字的非统一版本并执行 在列表索引位置上携带增量:
当你有 n
个列表时,你在这些列表中有 n
个索引位置:
index_pos = [i0, ..., in-1]
现在的技巧如下:
- 从
index_pos = [0, 0, ...]
开始
- 增量
index_pos[0]
。
- 如果结果大于或等于
lists[0].size()
,设置index_pos[0] = 0
并递增index_pos[1]
。
- 如果
index_pos[1]
大于或等于lists[1].size()
...等等
- 当
index_pos[n - 1]
溢出时你就完成了
Java 中的非递归解决方案就像
public static <T> void permute(
final List<List<T>> lists,
final Consumer<List<T>> consumer
)
{
final int[] index_pos = new int[lists.size()];
final int last_index = lists.size() - 1;
final List<T> permuted = new ArrayList<T>(lists.size());
for (int i = 0; i < lists.size(); ++i) {
permuted.add(null);
}
while (index_pos[last_index] < lists.get(last_index).size()) {
for (int i = 0; i < lists.size(); ++i) {
permuted.set(i, lists.get(i).get(index_pos[i]));
}
consumer.accept(permuted);
for (int i = 0; i < lists.size(); ++i) {
++index_pos[i];
if (index_pos[i] < lists.get(i).size()) {
/* stop at first element without overflow */
break;
} else if (i < last_index) {
index_pos[i] = 0;
}
}
}
}
用法示例:
public static void main(String[] args)
{
final List<List<Integer>> lists = new ArrayList<List<Integer>>();
final List<Integer> list0 = new ArrayList<Integer>();
list0.add(0);
list0.add(1);
list0.add(2);
list0.add(4);
lists.add(list0);
lists.add(list0);
lists.add(list0);
permute(lists, (permutation -> System.out.println(permutation)));
}
我有 n
个列表,例如:
L_1 = [a_11, a_12, ...]
L_2 = [a_21, a_22, ...]
...
L_n = [a_n1, a_n2, ...]
其中第 i
个列表有 k_i
个元素。
现在,我想生成所有 n
元素列表,其中 i
th 元素来自 L_i
,我的意思是:
[a_11, a_21, ..., a_n1]
[a_11, a_21, ..., a_n2]
...
[a_11, a_22, ..., a_n1]
[a_11, a_22, ..., a_n2]
...
[a_12, a_21, ..., a_n1]
[a_12, a_21, ..., a_n2]
...
[a_12, a_22, ..., a_n1]
[a_12, a_22, ..., a_n2]
...
列表总数应等于k_1*k_2*...k_n
。您能否描述该算法的伪代码或使用 Java 代码?当列表数量被硬编码时,我可以使用嵌套的 for 循环来做到这一点,但是当 n
在运行时可自定义时,我完全被阻止了。
好的,我实现了这个算法。
import com.google.common.collect.Lists;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class PermutationGenerator {
private List<List<Integer>> result;
private List<List<Integer>> data;
public List<List<Integer>> permutate(List<List<Integer>> data) {
this.data = data;
this.result = Lists.newArrayList();
List<Integer> integers = new ArrayList<Integer>(Collections.nCopies(data.size(), 0));
foo(0, data.size() - 1, integers);
return result;
}
private void foo(Integer index, Integer maxIndex, List<Integer> output) {
List<Integer> list = data.get(index);
for (int i = 0; i < list.size(); i++) {
output.set(index, list.get(i));
if (index == maxIndex) {
result.add(Lists.newArrayList(output));
} else {
foo(index + 1, maxIndex, output);
}
}
}
}
测试class:
import com.google.common.collect.Lists;
import org.junit.Test;
import java.util.Arrays;
import java.util.List;
public class PermutationGeneratorTest {
@Test
public void test() throws Exception {
// given
PermutationGenerator pg = new PermutationGenerator();
List<Integer> list1 = Lists.newArrayList(1, 2, 3);
List<Integer> list2 = Lists.newArrayList(4, 5);
List<Integer> list3 = Lists.newArrayList(6, 7, 8, 9);
List<List<Integer>> input = Lists.newArrayList(list1, list2, list3);
// when
List<List<Integer>> output = pg.permutate(input);
// then
print(output);
}
private void print(List<List<Integer>> output) {
for (List<Integer> list : output) {
System.out.println(Arrays.toString(list.toArray()));
}
System.out.println("TOTAL: " + output.size());
}
}
输出:
[1, 4, 6]
[1, 4, 7]
[1, 4, 8]
[1, 4, 9]
[1, 5, 6]
[1, 5, 7]
[1, 5, 8]
[1, 5, 9]
[2, 4, 6]
[2, 4, 7]
[2, 4, 8]
[2, 4, 9]
[2, 5, 6]
[2, 5, 7]
[2, 5, 8]
[2, 5, 9]
[3, 4, 6]
[3, 4, 7]
[3, 4, 8]
[3, 4, 9]
[3, 5, 6]
[3, 5, 7]
[3, 5, 8]
[3, 5, 9]
TOTAL: 24
正如您自己发现的那样,通常的 技巧是将列表视为 g-adic 数字的非统一版本并执行 在列表索引位置上携带增量:
当你有 n
个列表时,你在这些列表中有 n
个索引位置:
index_pos = [i0, ..., in-1]
现在的技巧如下:
- 从
index_pos = [0, 0, ...]
开始
- 增量
index_pos[0]
。- 如果结果大于或等于
lists[0].size()
,设置index_pos[0] = 0
并递增index_pos[1]
。 - 如果
index_pos[1]
大于或等于lists[1].size()
...等等
- 如果结果大于或等于
- 当
index_pos[n - 1]
溢出时你就完成了
Java 中的非递归解决方案就像
public static <T> void permute(
final List<List<T>> lists,
final Consumer<List<T>> consumer
)
{
final int[] index_pos = new int[lists.size()];
final int last_index = lists.size() - 1;
final List<T> permuted = new ArrayList<T>(lists.size());
for (int i = 0; i < lists.size(); ++i) {
permuted.add(null);
}
while (index_pos[last_index] < lists.get(last_index).size()) {
for (int i = 0; i < lists.size(); ++i) {
permuted.set(i, lists.get(i).get(index_pos[i]));
}
consumer.accept(permuted);
for (int i = 0; i < lists.size(); ++i) {
++index_pos[i];
if (index_pos[i] < lists.get(i).size()) {
/* stop at first element without overflow */
break;
} else if (i < last_index) {
index_pos[i] = 0;
}
}
}
}
用法示例:
public static void main(String[] args)
{
final List<List<Integer>> lists = new ArrayList<List<Integer>>();
final List<Integer> list0 = new ArrayList<Integer>();
list0.add(0);
list0.add(1);
list0.add(2);
list0.add(4);
lists.add(list0);
lists.add(list0);
lists.add(list0);
permute(lists, (permutation -> System.out.println(permutation)));
}