javajava-8bijection

Return set of all bijections on the input set

the method: public static Set<Function<T,T>> bijectionsFinder(Set<T> d)

say d= {1,2,3}. We are supposed to find all bijections from d -> d and return a set of those bijections.

Im not sure how to start.

Main method:

public static void main(String... args) {
    Set<Integer> a_few = Stream.of(1, 2, 3).collect(Collectors.toSet());
    Set<Function<T, T>> bijections = bijectionsOf(a_few);
    bijections.forEach(aBijection -> {
       a_few.forEach(n -> System.out.printf("%d --> %d; ", n, aBijection.apply(n)));
       System.out.println();
    });
}

Expected output if d= {1,2,3} :

enter image description here

Solution

  • Bijection of the dataset to itself results in a set of Permutations of the given data.

    And each Bijection should meet the definition:

    For a pairing between X and Y (where Y need not be different from X) to be a bijection, four properties must hold:

    • each element of X must be paired with at least one element of Y,

    • no element of X may be paired with more than one element of Y,

    • each element of Y must be paired with at least one element of X, and

    • no element of Y may be paired with more than one element of X.

    I.e. in a valid Bijection every element should be paired, and none of the elements can be paired with more than one element.

    To approach this a problem in a way that is easier to digest, we can describe Bijections as objects.

    Let's define the following classes:

    While initializing a new instance of Bijection based on the given data (see the method init()) a List of Pairs is being created. To meet the definition shown above, the number of Pair is equal to the number of elements in the given dataset, and initially each Pair is being assigned with an element from the given dataset as its first element (a).

    During the process of generating permutations, each pair is being provided with the second element (b). To track the pair that needs to be changed, Bijection has a property cursor

    Both Bijection and Pair expose method copy() to facilitate the process of generating permutations.

    public class Bijection<T> {
    private List<Pair<T>> pairs;
    private int cursor;

    public Bijection(List<Pair<T>> pairs) {
        this.pairs = pairs;
    }

    public Bijection(List<Pair<T>> pairs, int cursor) {
        this.pairs = pairs;
        this.cursor = cursor;
    }
    
    public static <T> Bijection<T> init(Collection<T> source) {
        return new Bijection<>(
            source.stream().map(Pair::init).toList()
        );
    }
    
    public void add(T b) {
        if (cursor == pairs.size()) throw new IllegalStateException();
        
        pairs.get(cursor++).add(b);
    }
    
    public Bijection<T> copy() {
        
        return pairs.stream()
            .map(Pair::copy)
            .collect(Collectors.collectingAndThen(
                Collectors.toList(),
                list -> new Bijection<>(list, cursor)
            ));
    }
    
    @Override
    public String toString() {
        return "Bijection{ " + pairs.stream().map(Pair::toString).collect(Collectors.joining(", ")) + " }";
    }
    
    public static class Pair<T> {
        private T a;
        private T b;
        
        public Pair(T a, T b) {
            this.a = a;
            this.b = b;
        }
        
        public static <T> Pair<T> init(T a) {
            return new Pair<>(a, null);
        }
        
        public void add(T b) {
            this.b = b;
        }
        
        public Pair<T> copy() {
            return new Pair<>(a, b);
        }
        
        @Override
        public String toString() {
            return "Pair{" + a + " -> " + b + '}';
        }
    }
}

    Here's the logic for generating all possible Bijections (i.e. all Permutations of elements in the given dataset expressed as connected pairs) encapsulated into a utility class.

    It's a basic recursive implementation. The Base case of recursion is when provide source of data is empty, i.e. no elements left to use and Bijection (Permutation) gets added to the resulting list.

    As the source of data for generating Permutations, I'll use a LinkedHashSet (as suggested by @Rogue in a comment) because it facilitates removal of elements in constant time and guaranties consistent order of iteration.

    public static class Bijections {
    
    private Bijections() {}
    
    public static <T> List<Bijection<T>> getBijections(Collection<T> source) {
        Set<T> set = new LinkedHashSet<>(source);
        List<Bijection<T>> bijections = new ArrayList<>();
        
        permute(set, Bijection.init(set), bijections);
        
        return bijections;
    }
    
    public static <T> void permute(Set<T> source,
                                   Bijection<T> bijection, // <- current Bijection
                                   List<Bijection<T>> bijections) {
        
        if (source.isEmpty()) {
            bijections.add(bijection);
            return;
        }
        
        for (T next : source) {
            // generate a new bijection based on the existing one and update it (the initial bijection doesn't change)
            Bijection<T> bijectionToUpdate = bijection.copy();
            bijectionToUpdate.add(next);
            // create a copy of the source a remove the current element from the copy (since it has been already used)
            Set<T> updatedSource = new LinkedHashSet<>(source);
            updatedSource.remove(next);
            // perform recursive call
            permute(updatedSource, bijectionToUpdate, bijections);
        }
    }
}

    main()

    public static void main(String[] args) {
    Bijections.getBijections(List.of(1, 2, 3))
        .forEach(System.out::println);
}

    Output:

    Bijection{ Pair{1 -> 1}, Pair{2 -> 2}, Pair{3 -> 3} }
Bijection{ Pair{1 -> 1}, Pair{2 -> 3}, Pair{3 -> 2} }
Bijection{ Pair{1 -> 2}, Pair{2 -> 1}, Pair{3 -> 3} }
Bijection{ Pair{1 -> 2}, Pair{2 -> 3}, Pair{3 -> 1} }
Bijection{ Pair{1 -> 3}, Pair{2 -> 1}, Pair{3 -> 2} }
Bijection{ Pair{1 -> 3}, Pair{2 -> 2}, Pair{3 -> 1} }