3

Здравствуйте! Пожалуйста, помогите реализовать алгоритм.

Даны целые числа от N_MIN до N_MAX. Необходимо вычислить все возможные последовательности этих чисел, при условии, что одно число не должно повторяться в последовательности дважды. Длина последовательности варьируется от CH_MIN до CH_MAX.

Поработав своим скудным количеством извилин, я пришёл к выводу, что задача решается с помощью циклов. Моя недоделанная реализация:

        //Сначала будем создавать последовательности с размером n,
        //потом n+1 и так далее, пока не достигнем максимкльного размера
        for (; CH_MIN < CH_MAX; CH_MIN++)
        {
            //С каждой итерацией данного цикла будем добавлять число
            //к последовательности, пока её размер не достигнет CH_MIN
            for (int CH_CUR = 0; CH_CUR < CH_MIN; CH_CUR++)
            {
                String CHAIN = "";
                //Выбираем первое число последовательности (N_MIN)
                for (int i = N_MIN; i < N_MAX; i++)
                {
                    CHAIN += (i + "");
                    //Далее надо выбрать остальные числа последовательности,
                    //но я не знаю, как это сделать.
                }
            }
        }

Была идея делать массив с числами от N_MIN до N_MAX, при каждом добавлении числа к последовательности убирать добавленное число из массива, чтобы в нём остались допустимые для добавления числа (это я так пытаюсь избежать повторения чисел). Однако я так запутался, что не смог реализовать ни идею с массивом, ни с циклами.

1
  • Такие вопросы отвлекают от работы! :) Для начала можно попробовать переоборудовать генератор словаря паролей, где исходная строка "012..9abc..z" как бы задает N-ную систему счисления (N — длина исходной строки). Задаем «нуль»: 0, потом 1, и так до z (это «N-ое число», которое в 10-ной СС было бы равно 10 — последнее из ряда). Следующее будет 00, за ним — 01, 02 и так далее до zz — до максимального двухразрядного числа N-ой системы счисления. Да, нужно при всем не забывать, что цифры не должны повторяться. Но с 10-ми числами, очевидно, можно найти более оптимальное решение.
    – Bars
    24 янв 2015 в 15:35

2 ответа 2

2

1) Первоначальный стэк чисел.
2) 2 последовательно у нас уже есть готовые, первая и реверсная.

Дальше можно прикинуть кол-во вариантов, это будет кол-во позиций (длина стэка) в степени кол-во уникальных чисел.

Дальше, думаю, можно создать матрицу, в которой ряд - это уникальная последовательность, остается придумать, как ее заполнять. =)

3) Пока что придумал, надо сдвигать сначала вправо по кругу на одно позицию, тогда получим все варианты первой последовательности, но надо еще варианты с вертикальным сдвигом.

1

Вот вариант, правда на JS (fiddle; исправлена процедура определения длины всей последовательности):

function generateSequence(min, max)
    {
    var alphabet = [];
    for (var i = min; i <= max; i++)
        alphabet.push(i);

    var res = [];
    var cur = null;
    var n = max-min + 1;
    var size = n;

    for (var i = 1; i < n; i++)
        size += Math.pow(n, i + 1);

    function getNext(seq)
        {
        if (!seq)
            return [alphabet[0]];

        var index = -1;
        for (var i = 0; i <= seq.length; i++)
            {
            if (i == seq.length + 1)
                {
                seq[i] = alphabet[0];
                break;
                }

            index = alphabet.indexOf(seq[i]) + 1;
            if (index < alphabet.length)
                {
                seq[i] = alphabet[index];
                break;
                }
            else
                seq[i] = alphabet[0];
            }

        return seq;
        }

    var temp;
    for (var i = 0; i < size; i++)
        {
        cur = getNext(cur);
        temp = ',' + cur.join(',') + ',';
        if (!temp.match(/,([^,]+),\1|,([^,]+),(?=.*,\2,)/))
            res.push(cur.join('-').split('-').reverse().join('-'));
        }

    return res;
    }
4
  • @Bars, спасибо! Так как мне надо будет портировать этот код на Java, то задам ещё один вопрос: Что значит if (!seq)? Я просто в JS не очень силён, просто видно, что тут вы работаете с этой переменной как с Boolean, а потом как с Array.
    – Helisia
    25 янв 2015 в 15:37
  • 1
    @SuperCreeper, [преобразование-к-логическому-типу][1] [1]: learn.javascript.ru/ifelse#преобразование-к-логическому-типу
    – woesss
    25 янв 2015 в 21:19
  • @woesss, однако классная в JS проверка на null :D И последний вопрос: как я понял, в JavaScript массивы "резиновые", то есть их размер автоматически изменяется. Но в Javа строки if (i == seq.length + 1) { seq[i] = alphabet[0]; break; } Выкинут IndexOutOfBoundsException. Можно ли как нибудь это обойти?
    – Helisia
    25 янв 2015 в 21:33
  • Зато в Java есть ArrayList, к примеру. Я понимаю, что производительность несколько упадет. seq можно представлять строкой с разделителем — мне кажется, что так будет полегче, чем заменять на ArrayList. Размер res рассчитывается заранее: for (var i = 1; i < n; i++) size += Math.pow(n, i + 1); size будет несколько больше, чем на самом деле нужно, но, как водится — лучше перебдеть. Я не смог вывести простую формулу для подсчета кол-ва элементов с учетом того, что дублирующиеся «знаки» внутри самих элементов не должны повторяться.
    – Bars
    29 янв 2015 в 14:41

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.