Создание подстановок массива JavaScript

У меня есть массив из n различных элементов в javascript, я знаю, что есть n! возможные способы упорядочения этих элементов. Я хочу знать, что является самым эффективным (самым быстрым) алгоритмом для генерации всех возможных порядков этого массива?

У меня есть этот код:

var swap = function(array, frstElm, scndElm) {

    var temp = array[frstElm];
    array[frstElm] = array[scndElm];
    array[scndElm] = temp;
}

var permutation = function(array, leftIndex, size) {

    var x;

    if(leftIndex === size) {

        temp = "";

        for (var i = 0; i < array.length; i++) {
            temp += array[i] + " ";
        }

        console.log("---------------> " + temp);

    } else {

        for(x = leftIndex; x < size; x++) {
            swap(array, leftIndex, x);
            permutation(array, leftIndex + 1, size);
            swap(array, leftIndex, x);
        }
    }
}

arrCities = ["Sidney", "Melbourne", "Queenstown"];
permutation(arrCities, 0, arrCities.length);

И это работает, но я думаю, что замена каждого элемента, чтобы получить комбинации, немного дорогая память, я думал, что хороший способ сделать это - просто сосредоточиться на индексах массива и получить все перестановки чисел, я интересно, есть ли способ вычислить все из них без необходимости переключения элементов внутри массива? Я думаю, что рекурсивно можно получить все из них, мне нужна помощь.

Так, например, если у меня есть:

arrCities = ["Sidney", "Melbourne", "Queenstown"];

Я хочу, чтобы результат был следующим:

[[012],[021],[102],[120],[201],[210]]

или:

[[0,1,2],
 [0,2,1],
 [1,0,2],
 [1,2,0],
 [2,0,1],
 [2,1,0]]

Я читаю это: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Но Википедия никогда не умела объяснять. Я не очень-то понимаю, я должен сказать, что мой математический уровень не самый лучший.

javascript,arrays,recursion,permutation,

10

Ответов: 3

6

Эта функция perm(xs)возвращает все перестановки заданного массива:

const perm=xs=>{let ret=[];for(let i=0;i<xs.length;i=i+1){let rest=perm(xs.slice(0,i).concat(xs.slice(i+1)));if(!rest.length){ret.push([xs[i]])}else{for(let j=0;j<rest.length;j=j+1){ret.push([xs[i]].concat(rest[j]))}}}return ret};

5 ов

Используя метод «Куча» (вы можете найти его в этой статье, ссылки на которую ссылаются в вашей статье в Википедии), вы можете сгенерировать все перестановки из N элементов с сложностью выполнения в O (N!) И сложностью пространства в O (N). Этот алгоритм основан на элементах подкачки. AFAIK это так же быстро, как и получается, нет более быстрого метода вычисления всех перестановок.

Для реализации и примеров, пожалуйста, посмотрите мой недавний ответ на соответствующий вопрос «Перестановки в javascript» .

1

Это моя версия, основанная на коде le_m :

function permute(array) {
        Array.prototype.swap = function (index, otherIndex) {
                var valueAtIndex = this[index]

                this[index] = this[otherIndex]
                this[otherIndex] = valueAtIndex
        }

        var result = [array.slice()]

        , length = array.length

        for (var i = 1, heap = new Array(length).fill(0)
                ; i < length
        ;)
                if (heap[i] < i) {
                        array.swap(i, i % 2 && heap[i])
                        result.push(array.slice())
                        heap[i]++
                        i = 1
                } else {
                        heap[i] = 0
                        i++
                }

        return result
}

console.log(permute([1, 2, 3]))

Это моя рекурсивная реализация JavaScript по тому же алгоритму:

Array.prototype.swap = function (index, otherIndex) {
        var valueAtIndex = this[index]

        this[index] = this[otherIndex]
        this[otherIndex] = valueAtIndex
}

Array.prototype.permutation = function permutation(array, n) {
        array = array || this
        n = n || array.length

        var result = []

        if (n == 1)
                result = [array.slice()]
        else {
                const nextN = n - 1

                for (var i = 0; i < nextN; i++) {
                        result.push(...permutation(array, nextN))
                        array.swap(Number(!(n % 2)) && i, nextN)
                }

                result.push(...permutation(array, nextN))
        }

        return result
}

console.log([1, 2, 3].permutation())

JavaScript, массивы, рекурсия, перестановка,
Похожие вопросы
Яндекс.Метрика