java - 从一个原始整数列表生成混洗整数列表的算法

Question

有一个 x 唯一 Integers 的 ArrayList，我需要在 y 的 z ArrayList 之间随机分配它们尺寸。请记住:

• x y z 是变量值。
• 结果数组中的数字不能重复。
• 生成的列表不得包含相同的数字! (订购它们必须不同)
• 如果计算结果数组中的出现次数，则原始数组中的每个数字必须尽可能使用与其他数字相同的次数。
• 必须使用原数组的所有数字，没有一个它们不能不使用。
• 如果可能，必须在 Java 7 中工作。不是 100% 强制性的，但是...
• 生成的组合将用于类似于彩票的 Activity ，因此它们不能连续太多，而且必须非常随机。它们也会按从最小到最大的顺序排序。
• 最初我尝试生成所有可能的组合，目的是只获得所需的数量，但这是不可行的，因为如果您选择高值，例如 40 个数字与 11 个数字的组合，则有数百万个数字，CPU 会卡住计算很多的时间，所以我尝试开发一个更简单的算法而不计算所有组合(我在下面发布代码)。

一个示例是这样的，当您有一个包含 8 个元素的数组的原点并且您想要输出 3 个大小为 6 的数组时:

original arraylist: [1, 2, 3, 4, 5, 6, 7, 8]

resulting output: [7, 5, 3, 6, 4, 8], [7, 5, 1, 8, 2, 3], [8, 1, 2, 3, 4, 6]

我开发了一种算法，在评论中进行了解释。首先，我创建了一个包含总位置的数组，并计算每个数字必须重复多少次才能填充输出数组。然后我用每个数字重复必要的次数填充数组，如果数组未满(因为当我除以得到 placesByNumber 我四舍五入到整数)我用随机填充它来自原始数字集的数字。之后我打乱数字，最后我填充结果数组，记住我不能在每个结果数组中重复数字。

问题来了，有时，我遇到最后一个数组没有完全填满的情况，因为打乱后的 numbersGroup 变量的最后一个数字包含在最后一个数组中。

这是一个失败的例子:

original arraylist: [1, 2, 3, 4, 5, 6, 7, 8]

shuffled group of numbers for fill the resulting arrays:

[8, 2, 4, 4, 5, 7, 2, 3, 8, 2, 1, 5, 7, 1, 6, 3, 6, 1]

resulting arrays: (the third doesn't have 6 elements because 6 and 1 arecontained on it)

[[8, 2, 4, 5, 7, 3], [4, 2, 8, 1, 5, 7], [2, 1, 6, 3]]

我发现了一些非常丑陋的方法来解决它，但这些方法非常低效，我正在努力寻找一种更好、更有效的算法来实现这一点。

这是我的源代码:

public static List<List<Integer>> getOptimizedCombinations(List<Integer> numbers, int numbersPerCombination, int desiredCombinations){
    List<List<Integer>> result = new ArrayList<>();
    
    //calculate total places and how many places correspond to each number.
    int totalPlaces = numbersPerCombination * desiredCombinations;
    int placesByNumber = totalPlaces / numbers.size();
    
    //instantiating array with the total number of places
    Integer[] numbersGroup = new Integer[totalPlaces];
    
    //filling the array with the numbers, now we know how many times a number must be inside the array, 
    //so we put the numbers. First we do it in order, later we will shuffle the array.
    int pos = 0;
    for (int n : numbers) {
        for (int i=0; i<placesByNumber; i++) {
            numbersGroup[pos] = n;
            pos++;
        }
    }
    
    //if there are places for fill, we fill it with random numbers. This can be possible because when we divide the total places between the 
    //numbers size, it can give a decimal as a result, and we round it to lower binary number without decimals, so it is possible to
    //have non filled places.       
    if (pos<totalPlaces) {
        while(pos<totalPlaces) {                
            numbersGroup[pos] = numbers.get(getRandom(0, numbers.size()));
            pos++;              
        }
    }       
    
    shuffleArray(numbersGroup);
    
    //we instantiate the arraylists
    for (int i=0; i<desiredCombinations; i++) {
        result.add(new ArrayList<Integer>());
    }
                    
    //filling the arraylists with the suffled numbers
    for (int i=0; i<numbersGroup.length; i++) {
        for (int j=0; j<result.size(); j++) {
            //if the combination doesn't have the number and the combination is not full, we add the number
            if (!result.get(j).contains(numbersGroup[i]) && result.get(j).size()<numbersPerCombination) {
                result.get(j).add(numbersGroup[i]);
                break;
            }
        }
    }
    
    return result;
}

static void shuffleArray(Integer[] ar){
    Random rnd = new Random();
    for (int i = ar.length - 1; i > 0; i--)
    {
        int index = rnd.nextInt(i + 1);
        // Simple swap
        int a = ar[index];
        ar[index] = ar[i];
        ar[i] = a;
    }
}

public static int getRandom(int min, int max) {
    return (int)(Math.random() * max + min);
}

这样调用:

    ArrayList<Integer> numbers = new ArrayList<Integer>() {{ 
        add(1); 
        add(2);
        add(3); 
        add(4); 
        add(5); 
        add(6); 
        add(7);
        add(8);
    }};
    getOptimizedCombinations(numbers, 6, 3);

Answer 1

您可以使用 Stream 将打乱后的列表限制为 z 个元素:

List<Integer> numbers = Arrays.asList(1,2,3,4,5,6,7,8);

List<List<Integer>> result = new LinkedList<>();
for(int i = 0; i < y; i++) {
  Collections.shuffle(numbers);
  List<Integer> list = numbers.stream().limit(z).collect(Collectors.toList());
  result.add(list);
}

System.out.println(result);

也许可以用更优雅的方式完成，但输出应该是这样的:

[[2, 8, 7, 3, 4, 6], [4, 3, 6, 5, 2, 8], [5, 2, 4, 1, 6, 8]]