0

我正在尝试创建 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 循环按顺序执行此操作很容易（就像这里讨论的那样），但是这将在每次试验中产生相同的配对，没有变化或随机性。

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

4

1 回答 1

2

您需要做的第一个想法是拥有一个索引映射。假设您的字母表是小于 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;
    }

}
于 2013-07-12T22:16:03.587 回答