How to create all permutations of tuples without mixing them?

Question

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.

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.

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!

Valerievalerio

Answer 1

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.

Try it online!

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]

---

^{See also: Convert a map of lists into a list of maps}

Trachytic