如何在不混合的情况下创建元组的所有排列? [英] How to create all permutations of tuples without mixing them?
问题描述
我有以下问题:给定了 k 个不同的元组，每个元组由 n 个元素组成.元组的顺序是固定的.让我们把这些元组放在一个 k*n-matrix 中.我现在想要做的是对这个矩阵的所有不同排列进行排列，而不将元素从元组移动到不同的元组.
I have the following problem: There are k different tuples given and each tuple consists of n elements. The order of the tuples is fixed. Let's just put these tuples in a k*n-matrix. What I now want to do is to permute through all different permutations of this matrix without moving the elements from a tuple to a different tuple.
例如:假设我们有 t1、t2 和 t3 元组，其中 t1:= (a,b,c)、t2:= (d,e,f) 和 t3:= (g,h,i).元组的顺序是固定的，例如在这种情况下是 t1、t2、t3.因此，通过将元组放入我们的矩阵 M，我们的矩阵如下所示:(a, b, c), (d, e, f), (g, h, i) 第一个括号是第一行，第二个括号是第二行，第三个括号是第三行.M 的一种可能排列是:(b, a, c), (d, e, f), (g, h, i).另一种可能的排列是 (b, a, c), (d, e, f), (g, i, h).不允许置换 (a, d, b), (c, e, f), (g, i, h) 因为 d 属于第二个元组并且c 属于第一个元组.
For example: Let's say we have the tuples t1, t2 and t3 with t1:= (a,b,c), t2:= (d,e,f) and t3:= (g,h,i). The order of the tuples is fixed and would be for example in this case t1, t2, t3. So by putting the tuples into our matrix M our matrix looks like this: (a, b, c), (d, e, f), (g, h, i) with the first parentheses being the first row, the second parentheses being the second row and the thrid parentheses being the third row. One possible permutation of M would be: (b, a, c), (d, e, f), (g, h, i). Another possible permutation would be (b, a, c), (d, e, f), (g, i, h). The permutation (a, d, b), (c, e, f), (g, i, h) are not allowed because d belongs to the second tuple and c belongs to the first tuple.
我已经尝试过的是将所有元素放入一个数组中，然后对所有可能的排列进行排列，然后检查排列是否有效(意味着所有元素是否都在它们应该位于的元组中).但是对于我的问题的规模来说，这不起作用，因为时间复杂度太高了.
What I have already tried out is to just put all elements into one array and then permute through all possible permutations and to then check wether or wether not the permutation is valid (meaning wether all elements are in the tuple where they should be). But for my the size of my problems this doesn't work because the time complexity is way too high.
如果你能给我一些关于如何做到这一点的想法，那就太好了.我使用 Java，所以 Java 代码会很好，但伪代码也很好.现在一方面要注意:对于我的问题实例，排列的值是对称的.我的意思是置换 (a, b, c), (d, e, f), (g, h, i) 将与 (c, b, a), (f, e, d), (i, h, g) 因为只有对我来说，为了确定排列的值，哪个元素在哪个元素之后才重要.因此，如果您的解决方案能够以某种方式以对称方式生成解决方案，那就太好了，因为这样我可以将计算时间减半.但这只是一个旁注，我很乐意提供各种解决方案！
It would be great if you could give me some ideas on how to do this. I use Java so Java code would be nice but pseudocode is also nice. Now one side note: For my problem instances the values of the permutations are symmetric. What I mean by that is that the permutation (a, b, c), (d, e, f), (g, h, i) will have the same value as (c, b, a), (f, e, d), (i, h, g) because what only matters to me in order to determine the value of the permutation is which element comes after which element. So if your solution would somehow generate solutions in a symmetrical way this would be great because this way I could halve the computation time. But this is only a side note and I would be happy about solutions of all kinds!
推荐答案
如果您有一些值的列表，您可以收集这些值的 distinct 排列列表，如下所示.在这种情况下，3!== 6 排列.接下来，如果您有两个不同排列列表，您可以在稍微修改的版本中重复此算法.
If you have a list of some values, you can collect a list of distinct permutations of those values as follows. In this case, 3! == 6 permutations. Next, if you have two lists of distinct permutations, you can repeat this algorithm in a slightly modified version.
List<String> list = List.of("a", "b", "c");
List<Map<Integer, String>> listOfMaps = IntStream.range(0, list.size())
// Stream<List<Map<Integer,String>>>
.mapToObj(i -> IntStream.range(0, list.size())
// represent list elements
// as Map<Integer,String>
.mapToObj(j -> Map.of(j, list.get(j)))
// collect a list of maps
.collect(Collectors.toList()))
// intermediate output
//[{0=a}, {1=b}, {2=c}]
//[{0=a}, {1=b}, {2=c}]
//[{0=a}, {1=b}, {2=c}]
.peek(System.out::println)
// reduce a stream of lists to a single list
// by sequentially summing pairs of lists
.reduce((list1, list2) -> list1.stream()
// summation of pairs of elements,
// i.e. maps, from two lists
.flatMap(map1 -> list2.stream()
// filter out those keys
// that are already present
.filter(map2 -> map2.keySet().stream()
.noneMatch(map1::containsKey))
// join entries of two maps
.map(map2 -> {
Map<Integer, String> map =
new LinkedHashMap<>();
map.putAll(map1);
map.putAll(map2);
return map;
}))
// collect into a single list
.collect(Collectors.toList()))
.orElse(null);
// output:
// number of permutations
System.out.println(listOfMaps.size()); // 6
//list of map values
listOfMaps.stream().map(Map::values).forEach(System.out::println);
//[a, b, c]
//[a, c, b]
//[b, a, c]
//[b, c, a]
//[c, a, b]
//[c, b, a]
另见:将列表映射转换为映射列表
这篇关于如何在不混合的情况下创建元组的所有排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
