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

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

要求提供代码的问题必须表现出对所解决问题的最低限度的了解。包括尝试的解决方案、为什么它们不起作用以及预期结果。另请参阅:Stack Overflow question checklist

已关闭10 年前。

Improve this 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>，令人恶心。使用嵌套 for 循环顺序执行此操作很容易(就像 here 所讨论的那样)，但是这会在每次试验中产生相同的配对，没有多样性或随机性。

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

Answer 1

您首先需要做的是拥有一个索引映射。假设您的字母表是小于 30 的斐比诺西数字 (1,2,3,5,8,13,21)，并且您需要 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;
    }

}