[Solved] Independent cycles in permutation [closed]

Question

Start with the first number (digit), follow the mappings until you’re back to the first number. That’s your first cycle.

Then start with the next number that hasn’t been visited yet, and repeat the process.

Keep repeating until all numbers have been visited.

↓             Start at first number
1 2 3 4 5 6     1
5 3 2 6 4 1

*       ↓     1 maps to 5:
1 2 3 4 5 6     1 → 5
5 3 2 6 4 1

*     ↓ *     5 maps to 4:
1 2 3 4 5 6     1 → 5 → 4
5 3 2 6 4 1

*     * * ↓   4 maps to 6:
1 2 3 4 5 6     1 → 5 → 4 → 6
5 3 2 6 4 1

*     * * *   6 maps to 1:
1 2 3 4 5 6     1 → 5 → 4 → 6 → 1
5 3 2 6 4 1     First cycle complete

* ↓   * * *   Start at first unvisited number:
1 2 3 4 5 6     2
5 3 2 6 4 1

* * ↓ * * *   2 maps to 3:
1 2 3 4 5 6     2 → 3
5 3 2 6 4 1

* * * * * *   3 maps to 2:
1 2 3 4 5 6     2 → 3 → 2
5 3 2 6 4 1     Second cycle complete

All digits visited, result:
  1 → 5 → 4 → 6 and 2 → 3  ⇒  (1546)(23)

Now you just need to write the code for this, in whichever language you prefer.

Hint: You will need 3 arrays, one for first set of numbers, one for second set of numbers, and an array to track which numbers have been visited.

You’ll also need something to capture the result, e.g. a StringBuilder if you use Java.

UPDATE

Here is a Java solution that supports negative and multi-digit numbers, with full input validation:

private static String findCycles(int[] a, int[] b) {
    if (a.length == 0)
        throw new IllegalArgumentException("The sets cannot be empty");
    if (a.length != b.length)
        throw new IllegalArgumentException("Sets must have same size: " + a.length + " != " + b.length);
    TreeMap<Integer, Integer> numIdx = IntStream.range(0, a.length).boxed()
            .collect(Collectors.toMap(i -> a[i], Function.identity(),
                                      (i1, i2) -> { throw new IllegalArgumentException("Duplicate numbers not allowed: " + a[i1]); },
                                      TreeMap::new));
    if (! IntStream.of(b).boxed().collect(Collectors.toSet()).equals(numIdx.keySet()))
        throw new IllegalArgumentException("Sets must consist of the same numbers");
    String separator = (numIdx.firstKey() < 0 || numIdx.lastKey() > 9 ? " " : "");
    BitSet used = new BitSet(a.length);
    StringBuilder result = new StringBuilder();
    for (int idx; (idx = used.nextClearBit(0)) < a.length; ) {
        StringJoiner cycle = new StringJoiner(separator, "(", ")");
        do {
            used.set(idx);
            cycle.add(String.valueOf(a[idx]));
            idx = numIdx.get(b[idx]);
        } while (! used.get(idx));
        result.append(cycle.toString());
    }
    return result.toString();
}

Test

// Example from question:
System.out.println(findCycles(new int[] { 1, 2, 3, 4, 5, 6 },
                              new int[] { 5, 3, 2, 6, 4, 1 }));

// Examples from https://en.wikipedia.org/wiki/Cyclic_permutation:
System.out.println(findCycles(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 },
                              new int[] { 4, 2, 7, 6, 5, 8, 1, 3 }));
System.out.println(findCycles(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 },
                              new int[] { 4, 5, 7, 6, 8, 2, 1, 3 }));
System.out.println(findCycles(new int[] { 1, 2, 3, 4 },
                              new int[] { 1, 4, 3, 2 }));

// Support for negative and multi-digit values:
System.out.println(findCycles(new int[] { -5, 0, 5, 10, 15, 20 },
                              new int[] { 0, 5, -5, 10, 20, 15 }));

Output

(1546)(23)
(146837)(2)(5)
(14625837)
(1)(24)(3)
(-5 0 5)(10)(15 20)

Accepted Answer