从一个原始整数列表生成洗牌整数列表的算法

Question

有一个xuniqueIntegers的数组列表，我需要将它们在yz大小的数组列表之间随机分布。请记住：

• x y z是可变值

一个html" target="_blank">示例是，当您有一个由8个元素组成的数组的原点，并且希望输出3个大小为6的数组时：

原始数组列表：[1, 2, 3, 4, 5, 6, 7, 8]

结果输出：[7,5,3,6,4,8]，[7,5,1,8,2,3]，[8,1,2,3,4,6]

我开发了一个算法，并在注释中进行了解释。首先，我创建了一个包含总位置的数组，并计算每个数字必须重复多少次才能填充输出数组。然后我用每个重复了必要次数的数字填充数组，如果数组没有满（因为当我除法得到placesByNumber时，我将四舍五入为整数），我将用原始数字集中的随机数填充数组。在那之后我洗牌数字，最后在那之后我填充结果数组，记住我不能在每个结果数组中重复数字。

有时，问题出现在这里，我得到的情况是，最后一个数组没有完全填充，因为被洗牌的numbersGroup变量的最后一个数字包含在最后一个数组中。

这是一个失败的例子：

原始数组列表：[1, 2, 3, 4, 5, 6, 7, 8]

用于填充结果数组的随机数字组：

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

结果数组：（第三个数组没有6个元素，因为其中包含6和1）

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

我的方法是打乱原始列表，然后不断迭代，直到填充目标列表，然后打乱每个目标列表。这将保持每个数字的出现平衡。它也可以工作，如果数字的组合

public class FairLists {

    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8);
        List<List<Integer>> fairLists = getOptimizedCombinations(numbers, 6, 3);
        System.out.println(fairLists);
    }

    public static List<List<Integer>> getOptimizedCombinations(List<Integer> numbers, int numbersPerCombination, int desiredCombinations){
        List<Integer> source = new ArrayList<>(numbers);
        Collections.shuffle(source);

        List<List<Integer>> fairNumbersLists = new ArrayList<>(desiredCombinations);

        int sourceIndex = 0;
        while (desiredCombinations > 0) {

            List<Integer> fairNumbers = new ArrayList<>(numbersPerCombination);
            for (int i = 0; i < numbersPerCombination; i++) {
                fairNumbers.add(source.get(sourceIndex));
                sourceIndex++;
                if (sourceIndex == source.size()) {
                    sourceIndex = 0;
                }
            }

            Collections.shuffle(fairNumbers);
            fairNumbersLists.add(fairNumbers);

            desiredCombinations--;
        }

        Collections.shuffle(fairNumbersLists);
        return fairNumbersLists;
    }
}

Answer 2

为了让这一切顺利进行，我们需要

• z

我们的想法是

1. 洗牌输入列表

输入

1 2 3 4 5 6 7 8

洗牌

3 5 8 6 7 2 4 1

重复一遍

3 5 8 6 7 2 4 1 3 5 8 6 7 2 4 1 3 5 8 6 7 2 4 1

分裂

3 5 8 6 7 2    4 1 3 5 8 6    7 2 4 1 3 5    8 6 7 2 4 1

洗牌每个列表

7 3 5 6 2 8    1 3 4 8 6 5    3 4 1 5 7 2    2 7 4 1 8 6

洗牌列表列表

1 3 4 8 6 5    2 7 4 1 8 6    7 3 5 6 2 8    3 4 1 5 7 2

这个程序应该在Java7中工作。然而，我只使用Java11对其进行了测试。

import java.util.*;
public class Shuffle {
    public static void main(String[] args) {
        System.out.println(splitShuffle(Arrays.asList(1,2,3,4,5,6,7,8), 6, 3));
    }
    public static List<List<Integer>> splitShuffle(
            List<Integer> input, int newLength, int listCount) {        
        assert newLength * listCount % input.size() == 0 : "Cannot distribute numbers evenly";
        input = new ArrayList<>(input);
        Collections.shuffle(input);
        List<List<Integer>> result = new ArrayList<>(listCount);
        for (int i = 0; i < listCount; ++i) {
            result.add(rotatingCopy(input, i * newLength, newLength));
        }
        Collections.shuffle(result);
        return result;
    }
    private static List<Integer> rotatingCopy(List<Integer> input, int startIndex, int length) {
        assert length < input.size() : "copy would have to contain duplicates";
        List<Integer> copy = new ArrayList<>(length);
        for (int i = 0; i < length; ++i) {
            copy.add(input.get((startIndex + i) % input.size()));
        }
        Collections.shuffle(copy);
        return copy;
    }
}

我运行了四次程序。以下是它的产出。每行是程序的一次运行。

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

我们可以看到，每个数字正好出现两次，每个子列表只有唯一的数字。

至少对于输入列表[1,2,3]和y=3，z=2我可以验证是否可以生成所有可能的48个输出。我知道使用以下bash命令有48种组合：

printf %s\\n {1..3}{1..3},{1..3}{1..3},{1..3}{1..3} | grep -Pv '(\d)\1' |
tr -d , | awk '{print $1, gsub(1,""), gsub(2,""), gsub(3,"")}' |
grep -F ' 2 2 2' | cut -d' ' -f1 | sort -u | wc -l

Answer 3

您可以使用Streams将随机列表限制为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]]