Помогите реализовать алгоритм

Рейтинг: 3Ответов: 2Опубликовано: 24.01.2015

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

Даны целые числа от 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, при каждом добавлении числа к последовательности убирать добавленное число из массива, чтобы в нём остались допустимые для добавления числа (это я так пытаюсь избежать повторения чисел). Однако я так запутался, что не смог реализовать ни идею с массивом, ни с циклами.

java алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 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;
    }
▲ 2

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

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

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

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