返回输入集上所有双射的集合

Question

方法：

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

说 d= {1,2,3}。我们应该找到 d -> d 中的所有双射并返回一组这些双射。

我不知道如何开始。

主要方法：

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();
    });
}

如果 d= {1,2,3} 则预期输出：

Answer 1

数据集对其自身的双射会产生一组给定数据的排列。

并且每个双射都应该满足定义：

对于

X

和

Y

之间的配对（其中

Y

不必不同） 来自

X

）要成为双射，必须满足四个属性：

• X

  的每个元素必须与

  Y

  ，
  中的至少一个元素配对

• X

  中的任何元素都不能与

  Y

  、
  中的多个元素配对

• Y

  的每个元素必须与

  X

  中的至少一个元素配对， 和

• Y

  中的任何元素都不能与

  X

  中的多个元素配对。

即在有效的双射中，每个元素都应该配对，并且任何元素都不能与多个元素配对。

为了以更容易理解的方式解决这个问题，我们可以将双射描述为对象。

让我们定义以下类：

• Bijection

  - 表示给定数据集对其自身的双射。由于双射由成对的元素组成，因此

  Bijection

  的实例保存对

  Pair

  列表的引用。

• Pair

  - 表示双射中的一对元素。

在根据给定数据初始化

Bijection

的新实例时（参见方法

init()

），正在创建

List

的

Pair

。为了满足上面所示的定义，

Pair

的数量等于给定数据集中的元素数量，并且最初每个

Pair

都被分配给定数据集中的一个元素作为其第一个元素（

a

） .

在生成排列的过程中，每对都被提供了第二个元素（

b

）。为了跟踪需要更改的对，

Bijection

有一个属性

cursor

Bijection

和

Pair

都公开方法

copy()

以促进生成排列的过程。

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 + '}';
        }
    }
}

这是生成所有可能的双射的逻辑（即给定数据集中元素的所有排列表示为连接对）封装到实用程序类中。

这是一个基本的递归实现。递归的基本情况是当提供的数据源为空时，即没有剩余元素可供使用，并且双射（排列）被添加到结果列表中。

作为生成排列的数据源，我将使用

LinkedHashSet

（如@Rogue在评论中建议的那样），因为它有助于在恒定时间内删除元素并保证一致的迭代顺序。

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);
}

输出：

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} }