从没有重复对的有限集创建整数对

Question

我试图创建30对整数，每个整数从一个有限的集合中随机抽取，没有重复的对。

例如，整数1- 10可以用(我认为...) 45种不同的方式配对，而不会创建重复的配对：<1,2> <1,3> <1,4> <1,5> <1,6> <1,7> <1,8> <1,9> <1,10> <2,3> <2,4>，ad nauseam。使用嵌套的for循环顺序执行此操作将很容易(就像前面讨论的here一样)，然而，这将在每次试验中产生相同的配对，没有多样性或随机性。

这些集合可以是10,000个整数，因此创建所有可能的排列，然后从该集合中随机抽取，将是不切实际的。每次比赛只会抽出30对。我是用Java编写的，但只要功能可以移植，任何语言都可以。

Answer 1

你需要做的第一件事就是建立一个索引映射。假设你的字母表是小于30 (1,2,3,5,8,13,21)的fibinoci数字，你需要5个配对。我们需要做的第一件事是将这些映射到索引0 .. n。为此，我们可以使用数组或列表等。

int[] mapping = { 1,2,3,5,8,13,21 };

接下来，我们需要一个容器类

class Pair {
    int a;
    int b;
    Pair(int a, int b) { this.a = a; this.b = b; }
    public boolean equals(Object o) {
        if(o instanceof Pair) {
            Pair p = (Pair)o;
            if(a == p.a && b == p.b) return true;
            // check reverse, as per comment from @Chance
            if(a == p.b && b == p.a) return true;
        }
        return false;
    }
    // poor hashcode, for sure, but we need hash(a,b) == hash(b,a)...
    public int hashCode() { return a ^ b; }
}

现在，我们可以使用随机数生成器根据我们的映射创建它们：

Random rand = new Random(); // in the class or something?
Set<Pair> generatePairs(int[] alphabet, int num) {
    Set<Pair> set = new HashSet<>();
    int size = alphabet.length * alphabet.length; // pretend it's a matrix 
    while(set.size() < num) {
        int both = random.nextInt(size); // only works up to alphabet.length < 2^15
        int apos = both % alphabet.length;
        int bpos = both / alphabet.length;
        int a = alphabet[a];
        int b = alphabet[b];
        Pair pair = new Pair(a,b);
        set.add(pair);
    }
    return set;
}

我整理了一个完整的可运行示例：

c:\files\j>javac Uniques.java

c:\files\j>java Uniques
Pair (5,5)
Pair (13,13)
Pair (7,7)
Pair (17,19)
Pair (7,2)
Pair (17,23)
Pair (11,3)
Pair (23,29)
Pair (29,17)
Pair (11,5)
Pair (19,2)
Pair (13,29)
Pair (3,17)
Pair (23,5)
Pair (2,23)
Pair (7,19)
Pair (5,19)
Pair (29,5)
Pair (13,17)
Pair (13,19)

源代码：

import java.util.*;
class Uniques {

    static class Pair {
        int a;
        int b;
        Pair(int a, int b) { this.a = a; this.b = b; }
        public boolean equals(Object o) {
            if(o instanceof Pair) {
                Pair p = (Pair)o;
                if(a == p.a && b == p.b) return true;
                // check reverse, as per comment from @Chance
                if(a == p.b && b == p.a) return true;
            }
            return false;
        }
        // poor hashcode, for sure, but we need hash(a,b) == hash(b,a)...
        public int hashCode() { return a ^ b; }
        public String toString() { return "Pair (" + a + "," + b + ")"; }
    }

    static Random rand = new Random(); // in the class or something?
    static Set<Pair> generatePairs(int[] alphabet, int num) {
        Set<Pair> set = new HashSet<Pair>();
        int size = alphabet.length * alphabet.length; // pretend it's a matrix 
        while(set.size() < num) {
            int both = rand.nextInt(size); // only works up to alphabet.length < 2^15
            int apos = both % alphabet.length;
            int bpos = both / alphabet.length;
            int a = alphabet[apos];
            int b = alphabet[bpos];
            Pair pair = new Pair(a,b);
            set.add(pair);
        }
        return set;
    }

    public static void main(String...args) {
        int[] nums = new int[10];
        int p = 2;
        // seed with prime numbers up to 10000
        for(int i = 0; i < nums.length; i++) {
            while(!isPrime(p)) p++;
            nums[i] = p++;
        }
        // just double checking I don't suck at isPrime() haha
        //for(int i : nums) System.out.println(i);

        // okay we have our numbers, now let's get some stuff out of them
        Set<Pair> pairs = generatePairs(nums, 20);
        for(Pair pair : pairs) System.out.println(pair);
    }

    public static boolean isPrime(int p) {
        if(p == 2) return true;
        if(p % 2 == 0) return false;
        int q = (int)(Math.sqrt(p) + 1);
        for(int i = 3; i < q; i +=2) {
            if(p % i == 0) return false;
        }
        return true;
    }

}