Generieren von Permutationen von JavaScript-array

Habe ich ein array von n verschiedenen Elementen in javascript, ich weiß, es gibt n! mögliche Wege, um diese Elemente. Ich will wissen, was am effektivsten (schnellsten) Algorithmus zur Generierung aller möglichen Ordnungen von diesem array?

Habe ich diesen code:

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);

Und es funktioniert, aber ich denke, etwa alle Element, um die Kombinationen ist ein bisschen teuer, Speicher-Weise, ich dachte, ein guter Weg, es zu tun, ist nur die Konzentration auf die Indizes des Arrays und alle Permutationen der zahlen Frage ich mich, ob es einen Weg gibt, der computing-alle von Ihnen, ohne Schalter-Elemente innerhalb des Arrays? Ich denke, rekursiv möglich ist, zu erhalten Sie alle, ich brauche Hilfe, dies zu tun.

So zum Beispiel, wenn ich habe:

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

Ich soll die Ausgabe sein:

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

oder:

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

Lese ich dies:
http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Aber Wikipedia hat noch nie gut im erklären. Ich verstehe nicht viel davon, ich muss sagen, mein Mathe-Niveau ist nicht die beste.

Mögliche Duplikate von Permutationen in javascript?
Erklären Sie bitte, was meinen Sie mit "effektivsten". Schnellste? Niedrigste Speichernutzung?
Es gibt nicht n! Permutationen, es sei denn, Sie absolut sicher sind, dass alle n Elemente im array sind voneinander Verschieden (oder besser erkennbar). Wenn zwei Elemente zu unterscheiden sind Sie schon weniger als n! Permutationen (in der Tat, müssen Sie Permutationen mit Wiederholungen).
ist nicht das gleiche, ich will es tun, die durch den index nicht von element
Nicht wirklich sicher, wie Sie es anders. Ersetzen Sie den Namen mit zahlen und es ist das gleiche problem.
diese Methode hat zum wechseln der Elemente im array zu erreichen, alle Permutationen, die ich denke, ist zu teuer Geschwindigkeit (und Speicher) weiser, ich bin nicht gut in Mathe, aber meine Logik sagt mir, es sollte eine Methode zur Berechnung aller möglichen Anzahl innerhalb einer Bandbreite und wäre schneller Weg, als dass Sie tatsächlich verschieben jedes element
Natürlich, können Sie herausfinden, wie viele es sind, ganz einfach, das ist nur eine Formel. Aber Sie müssen noch um die Ausgabe zu erzeugen. Das ist immer noch das gleiche problem. Ob strings oder zahlen, sind Sie immer noch eindeutig identifizierbare Dinge, die Sie generieren möchten Permutationen für.

InformationsquelleAutor DSB | 2016-06-01

Dieser Funktion perm(xs), gibt alle Permutationen einer gegebenen array:

JS:

function 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;
}

console.log(perm([1,2,3]).join("\n"));

InformationsquelleAutor chacmoolvm

5

Heap-Methode (Sie finden es in diesem Papier, die Ihre Wikipedia-Artikel verweist), können Sie die Generierung aller Permutationen von N Elementen mit Laufzeit-Komplexität von O(N!) und räumliche Komplexität in O(N). Dieser Algorithmus basiert auf swapping-Elemente. AFAIK ist dies so schnell, wie es kommt, es gibt keine schnellere Methode, um zu berechnen alle Permutationen.

Für eine Umsetzung und Beispiele, bitte haben Sie einen Blick bei meiner letzten Antwort auf die Frage im Zusammenhang mit "Permutationen in javascript".
- Was ist eine Methode, die tath nicht berechnen aller möglichen Permutationen, sondern macht einen ziemlich nahe Berechnung?
- Ich glaube nicht, dass ich verstehe. Wenn Sie nicht wollen, zu generieren, die alle Permutationen, aber nur wenige haben Sie einen Blick auf die Lehmer-code, die ermöglicht es Ihnen, schnell berechnen die einzelnen Permutationen gegeben eine lexikographische permutation index.
- Basic-test mit dieser Antwort (stackoverflow.com/a/37580979/1647737) lief 10 mal schneller als @chacmoolvm Antwort oben
InformationsquelleAutor le_m

Dies ist meine version basiert auf le_m's code:

JS:

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]))

Dies ist meine rekursive JavaScript-Implementierung des gleichen Algorithmus:

JS:

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())

InformationsquelleAutor Erik Engi

Es ist einfach nur zum Spaß - mein rekursive lösen in einem string

const perm = a => a.length ? a.reduce((r, v, i) => [ ...r, ...perm([ ...a.slice(0, i), ...a.slice(i + 1) ]).map(x => [ v, ...x ])], []) : [[]]

InformationsquelleAutor Boris Yuzhakov

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.