Расчет всех одноразовых комбинаций набора чисел - PullRequest
Новая
       11

Расчет всех одноразовых комбинаций набора чисел

0 голосов
/ 18 мая 2019

Лотерея Северной Каролины предлагает несколько розыгрышей, две из которых - «Выбор 3» и «Выбор 4». Вы выбираете 3 или 4 цифры соответственно от 0 до 9 (включительно), и числа могут повторяться (например, 9-9 -9 - допустимая комбинация). Я буду использовать выбор 3 для этого примера, потому что с ним легче работать, но я пытаюсь сделать это универсальным решением для работы с любым числом чисел.

Одной из особенностей Пика 3 и Пика 4 является «1-ВЫКЛ», что означает, что вы выигрываете приз, если хотя бы одно из выпавших чисел на 1 или 1 больше, чем на вашем билете.

Например, допустим, вы играли в пик 3 и выбрали 5-5-5 для своих чисел. Чтобы выиграть, нужно хотя бы одно число 1 (оффлайн 5-5-5, если вы играете в игру таким образом). Выигрышные комбинации будут: 

1 Number    2 Numbers    3 Numbers
--------    ---------    ---------
4-5-5       4-4-5        4-4-4
5-4-5       5-4-4        6-6-6
5-5-4       4-5-4        4-4-6
6-5-5       6-6-5        4-6-6
5-6-5       5-6-6        4-6-4
5-5-6       6-5-6        6-4-4
            4-5-6        6-6-4
            6-5-4        6-4-6
            6-4-5
            5-6-4
            5-4-6
            4-6-5

(я думаю, что это все комбинации, но вы поняли).

Самое «эффективное» решение, которое я мог бы придумать, - это иметь массивы, определяющие, какие числа изменены и как: 

int[][] alterations = {
    // 1 digit
    {-1, 0, 0}, {0, -1, 0}, {0, 0, -1}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1},
    // 2 digits
    {-1, -1, 0}, ...
};

А затем измените числа в соответствии с каждым из массивов изменений: 

int[] numbers = {5, 5, 5};
for(int i = 0; i < alterations.length; i++) {
    int[] copy = Arrays.copyOf(numbers, numbers.length);
    for(int j = 0; j < alterations[i].length; j++) {
        // note: this logic does not account for the numbers 0 and 9:
        // 1 down from 0 translates to 9, and 1 up from 9 translates
        // to 0, but you get the gist of how this is supposed to work
        copy[j] += alterations[i][j];
    }
    printArray(copy);
}

...

private static void printArray(int[] a) {
    String x = "";
    for(int i : a)
        x += i + " ";

    System.out.println(x.trim());
}

Но мне интересно, есть ли лучший способ сделать это. Кто-нибудь сталкивался с чем-то подобным и есть идеи получше?

1 Ответ

0 голосов
/ 18 мая 2019

Звучит так, будто вы ищете возврат, так как создание массива изменений довольно утомительно.В своем алгоритме обратного отслеживания вы создадите своих кандидатов, примените изменение и проверите, является ли полученная комбинация действительной, если да, то вы распечатали бы.Я предлагаю вам прочитать главу 7 Руководства по разработке алгоритмов Стивена Скиены, чтобы получить некоторую справочную информацию о возврате и узнать, как это можно сделать с комбинаторной задачей.

...