Алгоритм генерации списков перемешанных целых чисел из одного исходного списка целых чисел

Question

Имея ArrayList x уникального Integers, мне нужно распределить их в случайном порядке между y ArrayList размером z. Имейте в виду, что:

• x y z - значения переменных.
• Числа не могут повторяться в полученных массивах.
• Полученные списки не должны содержать одинаковые номера! (при заказе они должны быть разными)
• Каждое число исходного массива должно использоваться, насколько это возможно, столько же раз, сколько другие, если вы подсчитываете вхождения в результирующих массивах.
• Должны использоваться все числа исходного массива, ни одно из их нельзя использовать.
• Должно работать в Java 7, если это возможно. Не обязательно на 100%, но ...
• Полученные комбинации будут использоваться для чего-то похожего на лотерею, поэтому они не должны быть слишком последовательными и должны быть очень рандомизированы. Также они будут представлены отсортированными, от мин до макс.
• Изначально я попытался сгенерировать все возможные комбинации с целью получения только требуемой численности, но это нецелесообразно, потому что, если вы выберете высокие значения, такие как 40 чисел в комбинациях из 11, есть миллионы, и процессор застрянет, рассчитывая на много времени, поэтому я попытался разработать более простой алгоритм без расчета всех комбинаций (я публикую код ниже).

Один из примеров, например, если у вас есть источник массива из 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 Combination {

    private Combination() {
    }

    /**
     *
     * @param n:
     *            n-set
     * @param m:
     *            m-subset
     * @return number of combinations C(n, m) = (n(n - 1)...(n - m + 1)) / m!
     */
    public static BigInteger C(int n, int m) {
        if (m > n) {
            return BigInteger.ZERO;
        } else {
            if ((n - m) > m) {
                return C(n, (n - m));
            }
        }
        BigInteger numerator = BigInteger.ONE;
        BigInteger denominator = BigInteger.ONE;

        for (int i = n; i > m; i--) {
            numerator = numerator.multiply(BigInteger.valueOf(i));
        }

        for (int i = (n - m); i > 1; i--) {
            denominator = denominator.multiply(BigInteger.valueOf(i));
        }

        return numerator.divide(denominator);
    }

    /**
     *
     * @param <T>
     *            Type
     * @param elements
     *            List of elements to combine
     * @param numberOfRequiredElements
     *            must be less or equal to elements.size()
     * @param combinatios
     *            result: List&lt;List&lt;T&gt;&gt; of all combinations
     * @param temp
     *            used for recursive purposes
     * @return combinations<br>
     * 
     *         Example of usage:<br>
     *         List&lt;Integer&gt; elements = new ArrayList&lt;&gt;();<br>
     *         for (int i = 1; i &lt;= 7; i++) {<br>
     *         &emsp;elements.add(i);<br>
     *         }<br>
     *         List&lt;Integer&gt; temp = new ArrayList&lt;&gt;();<br>
     *         List&lt;List&lt;Integer&gt;&gt; combinations = new
     *         ArrayList&lt;&gt;();<br>
     *         System.out.println(Combination.allCombinations(elements, 6,
     *         combinations, temp));<br>
     *
     */
    public static <T> List<List<T>> allCombinations(List<T> elements, int numberOfRequiredElements,
            List<List<T>> combinatios, List<T> temp) {
        if (numberOfRequiredElements == 0) {
            // System.out.print(temp);
            combinatios.add(new ArrayList<>(temp));
        } else {
            for (int i = 0; i < elements.size(); i++) {
                temp.add(elements.get(i));
                List<T> subList = elements.subList(i + 1, elements.size());
                allCombinations(subList, numberOfRequiredElements - 1, combinatios, temp);
                temp.remove(temp.size() - 1);
            }
        }
        return combinatios;
    }

    /**
     *
     * @param args
     *            Not required for this purpose
     */
    public static void main(String[] args) {
        int NO_OF_ELEMENS = 10;
        int REQURED_COMBINATION_SIZE = 6;

        List<Integer> elements = new ArrayList<>();
        for (int i = 1; i <= NO_OF_ELEMENS; i++) {
            elements.add(i);
        }
        System.out.println("This is an example of using methods in this class\n");
        System.out.println("Elements are " + elements + " (size = " + elements.size() + ")");
        System.out.println("Requred size of combination is " + REQURED_COMBINATION_SIZE);
        System.out.println("Number of all combinations is " + Combination.C(NO_OF_ELEMENS, REQURED_COMBINATION_SIZE));
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> combinations = new ArrayList<>();
        System.out.println("All combinations are:");
        Combination.allCombinations(elements, REQURED_COMBINATION_SIZE, combinations, temp);
        int i = 0;
        for (List<Integer> combination : combinations) {
            System.out.println(++i + "\t" + combination);
        }
    }
}

Я надеюсь, что этот код может быть полезным. Постскриптум Извините за нечитаемые комментарии - я написал это ранее в NetBeans, а теперь использую IntelliJ ...

РЕДАКТИРОВАТЬ : Использование long вместо BigInteger для расчета количества комбинаций ... (Лично я не рекомендую это).

public static long noOfCombinations(int n, int m){

    //this part is for fewer multiplications
    //b/c 4 out of 6 has the same number of combinations as 2 out of 6
    if (m > n) {
        return 0;
    } else {
        if ((n - m) > m) {
            return noOfCombinations(n, (n - m));
        }
    }

    long numerator = 1;
    long denominator = 1;

    //these two loops are for partial factorial
    for (int i = n; i > m; i--) {
        numerator *= i;
    }

    for (int i = (n - m); i > 1; i--) {
        denominator *= i;
    }

    // no of combinations
    return numerator / denominator;
}

Answer 2

Идея

Чтобы сделать это, нам нужно

• z < x (длина каждого нового списка <длина входного списка) или мы не можем заполнить новые списки без дубликатов. </li>
• y·z (количество списков · длина списков) должно быть кратным x, иначе некоторые числа должны появляться чаще, чем другие.

Идея состоит в том, чтобы

1. Перемешать список ввода.
2. Повторите список ввода так, чтобы мы получили y·z числа. Это можно сделать без повторения списка. Хитрость заключается в использовании оператора по модулю %.
3. Равномерно разделить повторный список ввода на y списки длины z.
4. Перемешать каждый новый список.

Input

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

Split

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

Программа

Эта программа должна работать на Java 7. Однако я тестировал ее только на Java 11.

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 выходов могут быть сгенерированы. Я знаю, что есть 48 комбинаций с помощью следующей команды bash:

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

Мой подход состоит в том, чтобы перетасовать исходный список, затем непрерывно выполнять итерацию до тех пор, пока не будут заполнены целевые списки, а затем перемешать каждый целевой список. Это будет поддерживать вхождение каждого числа сбалансированным. Это также работает, если numbersPerCombination> numbers.size().

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 4

Вы можете использовать Stream s, чтобы ограничить перетасованный список 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]]