Permutasi di JavaScript?

147

Saya mencoba menulis fungsi yang melakukan hal berikut:

  • mengambil array bilangan bulat sebagai argumen (misalnya [1,2,3,4])
  • membuat sebuah larik dari semua kemungkinan permutasi [1,2,3,4], dengan setiap permutasi memiliki panjang 4

fungsi di bawah ini (saya menemukannya online) melakukan ini dengan mengambil string sebagai argumen, dan mengembalikan semua permutasi string itu

Saya tidak tahu bagaimana memodifikasinya untuk membuatnya bekerja dengan array bilangan bulat, (saya pikir ini ada hubungannya dengan bagaimana beberapa metode bekerja secara berbeda pada string daripada yang mereka lakukan pada bilangan bulat, tapi saya tidak yakin. ..)

var permArr = [], usedChars = [];
function permute(input) {
  var i, ch, chars = input.split("");
  for (i = 0; i < chars.length; i++) {
    ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length == 0)
      permArr[permArr.length] = usedChars.join("");
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};

Catatan: Saya ingin membuat fungsi mengembalikan array bilangan bulat , bukan array string .

Saya sangat membutuhkan solusi untuk berada di JavaScript. Saya sudah menemukan cara melakukan ini dengan python

javascript permutation pepperdreamteam
sumber

Jawaban:

109

Jika Anda perhatikan, kode sebenarnya membagi karakter menjadi array sebelum melakukan permutasi apa pun, jadi Anda cukup menghapus operasi gabungan dan pemisahan

var permArr = [],
  usedChars = [];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      permArr.push(usedChars.slice());
    }
    permute(input);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};


document.write(JSON.stringify(permute([5, 3, 7, 1])));
Luaskan cuplikan

Andreas Wong
sumber
@Tokopedia Sesuatu yang aneh terjadi pada saya mencoba menggunakan fungsi Anda. Saya menyimpannya di .js di mana saya memiliki semua "fungsi manipulasi daftar" saya. Jika saya menggunakannya dengan permute ([1,2,3]), dan kemudian permute ([4,5,6]), keluaran yang belakangan masih ada hasilnya, keluaran dari yang pertama. Tahu bagaimana cara memperbaikinya? Terimakasih banyak !
500
3
Ada pertanyaan baru tentang jawaban ini .
Anderson Green
19
Mengakses global di fungsi Anda, bentuknya buruk!
Shmiddty
132

Sedikit terlambat, tetapi ingin menambahkan versi yang sedikit lebih elegan di sini. Bisa berupa larik apa saja ...

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

Menambahkan versi ES6 (2015). Juga tidak mengubah larik input asli. Berfungsi di konsol di Chrome ...

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

Begitu...

permutator(['c','a','t']);

Hasil ...

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

Dan...

permutator([1,2,3]);

Hasil ...

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]
dibatasi
sumber
1
Jika Anda memiliki fungsi faktorial yang berguna (karena kemungkinan besar mempertimbangkan Anda berurusan dengan permutasi), Anda dapat mempercepatnya dengan mengubah inisialisasi lingkup luar menjadi var results = new Array(factorial(inputArr.length)), length=0, lalu ganti results.push(…)denganresults[length++]=…
Cyoce
1
Apa fungsi garis var cur, memo = memo || [];?
Ricevind
2
@ user2965967 Ini mendeklarasikan cur dan memo, dan menginisialisasi memo menjadi nilai memo, kecuali jika falsey (termasuk undefined), dalam hal ini akan menjadi array kosong. Dengan kata lain, ini adalah cara yang kurang ideal untuk memberikan parameter fungsi dengan nilai default.
Tuan Lavalamp
Ini mengubah larik asli.
Shmiddty
2
adalah slice()di permute(curr.slice(), m.concat(next))benar-benar diperlukan?
Yoav
87

Algoritme yang sangat efisien berikut ini menggunakan metode Heap untuk menghasilkan semua permutasi elemen N dengan kompleksitas waktu proses dalam O (N!):

function permute(permutation) {
  var length = permutation.length,
      result = [permutation.slice()],
      c = new Array(length).fill(0),
      i = 1, k, p;

  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      result.push(permutation.slice());
    } else {
      c[i] = 0;
      ++i;
    }
  }
  return result;
}

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

Algoritma yang sama diimplementasikan sebagai generator dengan kompleksitas ruang di O (N):

Tampilkan cuplikan kode

Perbandingan kinerja

Jangan ragu untuk menambahkan implementasi Anda ke rangkaian pengujian benchmark.js berikut :

Tampilkan cuplikan kode

Hasil run-time untuk Chrome 48:

le_m
sumber
1
Bagaimana kode ini diubah untuk memberikan hasil untuk n = 2 tetap? Sebagai contoh, misalkan kita memiliki himpunan yang terdiri dari tiga huruf: A, B, dan C. Kita mungkin bertanya berapa banyak cara kita dapat menyusun 2 huruf dari himpunan tersebut. Setiap pengaturan yang mungkin akan menjadi contoh permutasi. Daftar lengkap kemungkinan permutasi adalah: AB, AC, BA, BC, CA, dan CB.
a4xrbj1
1
@ a4xrbj1 Lihat misalnya contoh kode dalam pertanyaan ini: stackoverflow.com/questions/37892738/… - atau apakah Anda secara khusus menanyakan tentang cara mengubah metode (Heap) ini?
le_m
@le_m ya, secara khusus menggunakan metode (Heap) ini karena sangat cepat
a4xrbj1
@ a4xrbj1 Saya akan menghitung semua kombinasi dengan panjang tetap n (misalnya AB, AC, BC untuk n = 2) menggunakan strategi yang mirip dengan tautan yang diberikan di atas (lihat juga stackoverflow.com/questions/127704/… ) dan kemudian untuk setiap kombinasi hitung semua permutasinya menggunakan metode Heap. Kasus khusus seperti n = 2 tentu saja dapat dioptimalkan.
le_m
1
Versi generator tidak berfungsi dengan baik, Anda harus melakukannya yield permutation.slice()jika Anda tidak memotong Anda hanya mendapatkan permutasi terakhir yang dihitung.
Beldar
42 
var inputArray = [1, 2, 3];

var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);


alert(JSON.stringify(result));
monyet
sumber
11
Wow, meskipun dokumennya sempit dan kurang, saya rasa ini adalah jawaban yang paling elegan. Penjelasan saya tentang algoritme ini adalah: Untuk setiap item dalam array (kurangi), pilih semua item lainnya, permutasi (secara rekursif), dan satukan ke item ini.
aaron
Mencoba solusi ini di sini: codewars.com/kata/reviews/5254ca2719453dcc0b000280/groups/… Saya telah membuka bungkus kode golf asli menjadi kode yang dapat dibaca, tetapi pada dasarnya sama. Masalahnya adalah itu menghasilkan duplikat, dan saya harus melakukan tambahan .filter(uniq)pada hasilnya.
Andrey Mikhaylov - lolmaus
1
apakah ada cadel sejajar dengan konsep [1,2,3].length == 3 && "foo" || "bar"atau [1,2].length == 3 && "foo" || "bar"oh my! ada! (or (and (= 3 2) (print "hello!")) (print "goodbye"))
Dmitry
@ lolmaus-AndreyMikhaylov cara menghapus duplikat Harap Perbarui jawaban jika Anda bisa
Pardeep Jain
@PardeepJain Saya memberikan tautan ke solusi saya di atas.
Andrey Mikhaylov - lolmaus
21

Saya telah meningkatkan SiGanteng 's jawaban .

Sekarang dimungkinkan untuk menelepon permutelebih dari sekali, karena permArrdan usedCharsdibersihkan setiap kali.

function permute(input) {
    var permArr = [],
        usedChars = [];
    return (function main() {
        for (var i = 0; i < input.length; i++) {
            var ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main();
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr;
    })();
}

Tampilkan cuplikan kode

Oriol
sumber
11

Sebagian besar jawaban atas pertanyaan ini menggunakan operasi mahal seperti penyisipan berkelanjutan dan penghapusan item dalam larik, atau menyalin larik secara berulang.

Sebaliknya, ini adalah solusi mundur yang khas:

function permute(arr) {
  var results = [],
      l = arr.length,
      used = Array(l), // Array of bools. Keeps track of used items
      data = Array(l); // Stores items of the current permutation
  (function backtracking(pos) {
    if(pos == l) return results.push(data.slice());
    for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
      used[i] = true;      // Mark item as used
      data[pos] = arr[i];  // Assign item at the current position
      backtracking(pos+1); // Recursive call
      used[i] = false;     // Mark item as not used
    }
  })(0);
  return results;
}

permute([1,2,3,4]); // [  [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1]  ]

Karena larik hasil akan sangat besar, mungkin ide yang baik untuk mengulang hasil satu per satu daripada mengalokasikan semua data secara bersamaan. Di ES6, ini dapat dilakukan dengan generator:

function permute(arr) {
  var l = arr.length,
      used = Array(l),
      data = Array(l);
  return function* backtracking(pos) {
    if(pos == l) yield data.slice();
    else for(var i=0; i<l; ++i) if(!used[i]) {
      used[i] = true;
      data[pos] = arr[i];
      yield* backtracking(pos+1);
      used[i] = false;
    }
  }(0);
}

var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}
Oriol
sumber
10

Fungsi berikut mengubah array jenis apa pun dan memanggil fungsi panggilan balik yang ditentukan pada setiap permutasi yang ditemukan:

/*
  Permutate the elements in the specified array by swapping them
  in-place and calling the specified callback function on the array
  for each permutation.

  Return the number of permutations.

  If array is undefined, null or empty, return 0.

  NOTE: when permutation succeeds, the array should be in the original state
  on exit!
*/
  function permutate(array, callback) {
    // Do the actual permuation work on array[], starting at index
    function p(array, index, callback) {
      // Swap elements i1 and i2 in array a[]
      function swap(a, i1, i2) {
        var t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
      }

      if (index == array.length - 1) {
        callback(array);
        return 1;
      } else {
        var count = p(array, index + 1, callback);
        for (var i = index + 1; i < array.length; i++) {
          swap(array, i, index);
          count += p(array, index + 1, callback);
          swap(array, i, index);
        }
        return count;
      }
    }

    if (!array || array.length == 0) {
      return 0;
    }
    return p(array, 0, callback);
  }

Jika Anda menyebutnya seperti ini:

  // Empty array to hold results
  var result = [];
  // Permutate [1, 2, 3], pushing every permutation onto result[]
  permutate([1, 2, 3], function (a) {
    // Create a copy of a[] and add that to result[]
    result.push(a.slice(0));
  });
  // Show result[]
  document.write(result);

Saya pikir itu akan melakukan apa yang Anda butuhkan - mengisi sebuah array yang disebut resultdengan permutasi dari array [1, 2, 3]. Hasilnya adalah:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

Kode yang sedikit lebih jelas di JSFiddle: http://jsfiddle.net/MgmMg/6/

MarkusT
sumber
8

Beberapa versi yang terinspirasi dari Haskell:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]


function perms(xs) {
  if (!xs.length) return [[]];
  return xs.flatMap(x => {
    // get permutations of xs without x, then prepend x to each
    return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
  });
}
document.write(JSON.stringify(perms([1,2,3])));
Luaskan cuplikan

caub
sumber
6

Ini adalah tugas yang menarik dan inilah kontribusi saya. Ini sangat sederhana dan cepat. Jika tertarik, mohon bersabar dan baca terus.

Jika Anda ingin melakukan pekerjaan ini dengan cepat, Anda pasti harus masuk ke dalam pemrograman dinamis. Yang berarti Anda harus melupakan pendekatan rekursif. Itu sudah pasti...

OK le_m kode yang menggunakan metode Heap tampaknya menjadi yang tercepat sejauh ini. Saya belum punya nama untuk algoritme saya, saya tidak tahu apakah itu sudah diterapkan atau belum tetapi sangat sederhana dan cepat. Seperti semua pendekatan pemrograman dinamis, kita akan mulai dengan masalah yang paling sederhana dan melanjutkan ke hasil akhir.

Dengan asumsi bahwa kita memiliki array yang a = [1,2,3]akan kita mulai

r = [[1]]; // result
t = [];    // interim result

Kemudian ikuti tiga langkah berikut;

  1. Untuk setiap item dari rarray (result) kita, kita akan menambahkan item berikutnya dari array input.
  2. Kami akan memutar setiap item panjangnya berkali-kali dan akan menyimpan setiap contoh pada larik hasil sementara t . (baik kecuali yang pertama tidak membuang waktu dengan 0 rotasi)
  3. Setelah kita selesai dengan semua item dari rarray sementara tharus menahan tingkat hasil berikutnya sehingga kita membuat r = t; t = [];dan melanjutkan sampai panjang array masukan a.

Jadi berikut ini adalah langkah-langkah kami;

r array   | push next item to |  get length many rotations
          |  each sub array   |       of each subarray
-----------------------------------------------------------
[[1]]     |     [[1,2]]       |     [[1,2],[2,1]]
----------|-------------------|----------------------------
[[1,2],   |     [[1,2,3],     |     [[1,2,3],[2,3,1],[3,1,2],
 [2,1]]   |      [2,1,3]]     |      [2,1,3],[1,3,2],[3,2,1]]
----------|-------------------|----------------------------
previous t|                   |
-----------------------------------------------------------

Jadi inilah kodenya

function perm(a){
  var r = [[a[0]]],
      t = [],
      s = [];
  if (a.length <= 1) return a;
  for (var i = 1, la = a.length; i < la; i++){
    for (var j = 0, lr = r.length; j < lr; j++){
      r[j].push(a[i]);
      t.push(r[j]);
      for(var k = 1, lrj = r[j].length; k < lrj; k++){
        for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
        t[t.length] = s;
        s = [];
      }
    }
    r = t;
    t = [];
  }
  return r;
}

var arr = [0,1,2,4,5];
console.log("The length of the permutation is:",perm(arr).length);
console.time("Permutation test");
for (var z = 0; z < 2000; z++) perm(arr);
console.timeEnd("Permutation test");
Luaskan cuplikan

Dalam beberapa tes saya telah melihatnya menyelesaikan 120 permutasi [0,1,2,3,4] untuk 2000 kali dalam 25 ~ 35ms.

Redu
sumber
1
Tampaknya berjalan sangat cepat, terkadang lebih cepat, terkadang lebih lambat daripada metode Heap pada FF / Ubuntu untuk iterasi / pemanasan yang berbeda panjangnya, dll. Akan membutuhkan jsperf untuk melihat hasil untuk mesin yang berbeda.
le_m
1
@le_m OK saya telah melakukan beberapa tes @JSBen Pada Ubuntu & AMD CPU: Dengan Chrome rotatePerm(yang di atas) secara konsisten 1.2 lebih cepat. Dengan FF tidak ada konsistensi. Setelah beberapa tes terkadang heapPerm2 kali lebih cepat beberapa kali rotatePerm1,1 kali lebih cepat. Dengan browser kit web lain seperti Opera atau Epiphany rotatePermsecara konsisten ternyata 1,1 kali lebih cepat. Namun dengan Edge heapPermsecara konsisten 1,2 kali lebih cepat setiap saat.
Redu
1
Bagus! Tampaknya - setidaknya di FF / Ubuntu - performa metode heap terutama bergantung pada performa penyalinan array. Saya mengubah tolok ukur Anda untuk membandingkan pemotongan vs. mendorong: jsben.ch/#/x7mYh - di FF dan untuk larik input kecil, mendorong tampak jauh lebih cepat
le_m
2
Akan lebih bagus jika metode heap dapat dikalahkan dari segi performa. Omong-omong, metode Anda menghasilkan keluaran yang sama dengan algoritme Langdon (halaman 16) dari makalah 1977 yang sama yang saya gunakan sebagai referensi untuk metode Heap: homepage.math.uiowa.edu/~goodman/22m150.dir/2007/…
le_m
2
@le_m Saya baru saja memeriksa dan tampaknya hal yang sama. Sepertinya saya melakukan rotasi seperti yang dia lakukan. Hanya dengan penundaan 40 tahun. Seperti yang telah saya sebutkan dalam jawaban saya, ini sebenarnya metode yang sangat sederhana. Disebutkan menjadi pilihan hanya jika tersedia rotasi cepat. Saat ini saya masuk ke Haskell dan memiliki metode bawaan untuk membuat daftar (katakanlah array) siklus tanpa batas (evaluasi malas membuat pengulangan tak terbatas tidak masalah) dan ini mungkin berguna. Namun, Haskell sudah memiliki permutationsfungsi standar :)
Redu
6

Versi tercepat, paling (resorces) efektif dan paling elegan saat ini (2020)

function getArrayMutations (arr, perms = [], len = arr.length) {
  if (len === 1) perms.push(arr.slice(0))

  for (let i = 0; i < len; i++) {
    getArrayMutations(arr, perms, len - 1)

    len % 2 // parity dependent adjacent elements swap
      ? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]]
      : [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]]
  }

  return perms
}

const arrayToMutate = [1, 2, 3, 4, 5, 6, 7, 8, 9]

const startTime = performance.now()
const arrayOfMutations = getArrayMutations(arrayToMutate)
const stopTime = performance.now()
const duration = (stopTime - startTime) / 1000

console.log(`${arrayOfMutations.length.toLocaleString('en-US')} permutations found in ${duration.toLocaleString('en-US')}s`)
Luaskan cuplikan

Vladislav Ladicky
sumber
Hai, apakah Anda keberatan menjelaskan apa len % 2 // parity dependent adjacent elements swapartinya dan mengapa itu digunakan?
Pramesh Bajracharya
Kode saya menggunakan "algoritma Heap" untuk menghasilkan permutasi array. Jadi, jika Anda ingin mengetahui cara kerja kode saya, baca penjelasan algoritme Heap ini: en.m.wikipedia.org/wiki/Heap%27s_algorithm
Vladislav Ladicky
Apakah Anda mencoba mencetak hasilnya? bagaimana mengontrol maksimal jika elemen array lebih dari 10?
Marvix
5

Menjawab tanpa memerlukan larik eksterior atau fungsi tambahan

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}
Taylor Hakes
sumber
dapatkah Anda membuat kombinasi darinya? stackoverflow.com/questions/53555563/…
Techdive
5

Ini solusi yang keren

const rotations = ([l, ...ls], right=[]) =>
  l ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []

const permutations = ([x, ...xs]) =>
  x ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
  
console.log(permutations("cat"))
Luaskan cuplikan

Chris Vouga
sumber
2

Ini adalah solusi lain yang "lebih rekursif".

function perms(input) {
  var data = input.slice();
  var permutations = [];
  var n = data.length;

  if (n === 0) {
    return [
      []
    ];
  } else {
    var first = data.shift();
    var words = perms(data);
    words.forEach(function(word) {
      for (var i = 0; i < n; ++i) {
        var tmp = word.slice();
        tmp.splice(i, 0, first)
        permutations.push(tmp);
      }
    });
  }

  return permutations;
}

var str = 'ABC';
var chars = str.split('');
var result = perms(chars).map(function(p) {
  return p.join('');
});

console.log(result);
Luaskan cuplikan

Keluaran:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
licik
sumber
bisakah kamu membuat kombinasi untuk itu? stackoverflow.com/questions/53555563/…
Techdive
2 
   function perm(xs) {
       return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
        for (var i = 0; i < xs.length; i++) {
          acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
        }
        return acc;
      }, []);
    }

Uji dengan:

console.log(JSON.stringify(perm([1, 2, 3,4])));
eb58
sumber
2

Sebagian besar jawaban lain tidak memanfaatkan fungsi generator javascript baru yang merupakan solusi sempurna untuk jenis masalah ini. Anda mungkin hanya membutuhkan satu permutasi dalam memori. Selain itu, saya lebih suka menghasilkan permutasi dari berbagai indeks karena ini memungkinkan saya untuk mengindeks setiap permutasi dan langsung beralih ke permutasi tertentu serta digunakan untuk mengubah koleksi lainnya.

// ES6 generator version of python itertools [permutations and combinations]
const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; }
const isEmpty = arr => arr.length === 0;

const permutations = function*(a) {
    const r = arguments[1] || [];
    if (isEmpty(a)) yield r;
    for (let i of range(a.length)) {
        const aa = [...a];
        const rr = [...r, ...aa.splice(i, 1)];
        yield* permutations(aa, rr);
    }
}
console.log('permutations of ABC');
console.log(JSON.stringify([...permutations([...'ABC'])]));

const combinations = function*(a, count) {
    const r = arguments[2] || [];
    if (count) {
        count = count - 1;
        for (let i of range(a.length - count)) {
            const aa = a.slice(i);
            const rr = [...r, ...aa.splice(0, 1)];
            yield* combinations(aa, count, rr);
        }
    } else {
        yield r;
    }
}
console.log('combinations of 2 of ABC');
console.log(JSON.stringify([...combinations([...'ABC'], 2)]));



const permutator = function() {
    const range = function*(args) {
        let {begin = 0, count} = args;
        for (let i = begin; count; count--, i+=1) {
            yield i;
        }
    }
    const factorial = fact => fact ? fact * factorial(fact - 1) : 1;

    return {
        perm: function(n, permutationId) {
            const indexCount = factorial(n);
            permutationId = ((permutationId%indexCount)+indexCount)%indexCount;

            let permutation = [0];
            for (const choiceCount of range({begin: 2, count: n-1})) {
                const choice = permutationId % choiceCount;
                const lastIndex = permutation.length;

                permutation.push(choice);
                permutation = permutation.map((cv, i, orig) => 
                    (cv < choice || i == lastIndex) ? cv : cv + 1
                );

                permutationId = Math.floor(permutationId / choiceCount);
            }
            return permutation.reverse();
        },
        perms: function*(n) {
            for (let i of range({count: factorial(n)})) {
                yield this.perm(n, i);
            }
        }
    };
}();

console.log('indexing type permutator');
let i = 0;
for (let elem of permutator.perms(3)) {
  console.log(`${i}: ${elem}`);
  i+=1;
}
console.log();
console.log(`3: ${permutator.perm(3,3)}`);
Luaskan cuplikan

Doug Coburn
sumber
2 
#!/usr/bin/env node
"use strict";

function perm(arr) {
    if(arr.length<2) return [arr];
    var res = [];
    arr.forEach(function(x, i) {
        perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) {
            res.push([x].concat(a));
        });
    });
    return res;
}

console.log(perm([1,2,3,4]));
dashxdr
sumber
2

Ini yang saya buat ...

const permute = (ar) =>
  ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
    {permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);

Dan ini dia lagi tetapi ditulis dengan kurang singkat! ...

function permute(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
      .map(value=>accumulator.push([].concat(inputArray[index],value)));
    return accumulator;
  },[]);
}

Cara kerjanya: Jika array lebih panjang dari satu elemen, ia melangkah melalui setiap elemen dan menggabungkannya dengan panggilan rekursif ke dirinya sendiri dengan elemen yang tersisa sebagai argumennya. Itu tidak mengubah array asli.

Roger Heathcote
sumber
2

Jawaban fungsional menggunakan flatMap:

const getPermutationsFor = (arr, permutation = []) =>
  arr.length === 0
    ? [permutation]
    : arr.flatMap((item, i, arr) =>
        getPermutationsFor(
          arr.filter((_,j) => j !== i),
          [...permutation, item]
        )
      );
jabsatz
sumber
2

Kontribusi pertama saya ke situs. Juga, menurut tes yang telah saya lakukan, kode ini berjalan lebih cepat daripada semua metode lain yang disebutkan di sini sebelum tanggal ini, tentu saja minimal jika nilainya sedikit, tetapi waktu meningkat secara eksponensial saat menambahkan terlalu banyak.

function permutations(arr) {
    var finalArr = [];
    function iterator(arrayTaken, tree) {
        var temp;
        for (var i = 0; i < tree; i++) {
            temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else {
                iterator(temp, tree + 1);
            }
        }
    }
    iterator(arr, 1);
    return finalArr;
};
Urielzen
sumber
Saya menambahkan perbandingan kinerja stackoverflow.com/a/37580979/1647737 - silakan perbarui.
le_m
1 

"use strict";
function getPermutations(arrP) {
    var results = [];
    var arr = arrP;
    arr.unshift(null);
    var length = arr.length;

    while (arr[0] === null) {

        results.push(arr.slice(1).join(''));

        let less = null;
        let lessIndex = null;

        for (let i = length - 1; i > 0; i--) {
            if(arr[i - 1] < arr[i]){
                less = arr[i - 1];
                lessIndex = i - 1;
                break;
            }
        }

        for (let i = length - 1; i > lessIndex; i--) {
            if(arr[i] > less){
                arr[lessIndex] = arr[i];
                arr[i] = less;
                break;
            }
        }

        for(let i = lessIndex + 1; i<length; i++){
           for(let j = i + 1; j < length; j++){
               if(arr[i] > arr[j] ){
                   arr[i] = arr[i] + arr[j];
                   arr[j] = arr[i] - arr[j];
                   arr[i] = arr[i] - arr[j];
               }
           }
        }
    }

    return results;
}

var res = getPermutations([1,2,3,4,5]);
var out = document.getElementById('myTxtArr');
res.forEach(function(i){ out.value+=i+', '});
textarea{
   height:500px;
  width:500px;
}
<textarea id='myTxtArr'></textarea>
Luaskan cuplikan

Menghasilkan permutasi yang diurutkan secara leksikografis. Bekerja hanya dengan angka. Dalam kasus lain, Anda harus mengubah metode swap di baris 34.

tamaz bagdavadze
sumber
1

Semangat mirip dengan solusi gaya Haskell oleh @crl, tetapi bekerja dengan reduce:

function permutations( base ) {
  if (base.length == 0) return [[]]
  return permutations( base.slice(1) ).reduce( function(acc,perm) {
    return acc.concat( base.map( function(e,pos) {
      var new_perm = perm.slice()
      new_perm.splice(pos,0,base[0])
      return new_perm
    }))
  },[])    
}
rplantiko
sumber
1

Ini adalah kasus penggunaan yang sangat bagus untuk map / reduce:

function permutations(arr) {
    return (arr.length === 1) ? arr :
    arr.reduce((acc, cv, index) => {
        let remaining = [...arr];
        remaining.splice(index, 1);
        return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
    }, []);
}
  • Pertama, kami menangani kasus dasar dan mengembalikan array jika hanya ada satu item di dalamnya
  • Dalam semua kasus lainnya
    • kami membuat array kosong
    • loop di atas input-array
    • dan menambahkan array dari nilai saat ini dan semua permutasi dari array yang tersisa [].concat(cv,a)
danielbuechele
sumber
1

Ini adalah versi ES6 minimal. Fungsi datar dan tanpa fungsi dapat ditarik dari Lodash.

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));

Hasil:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Márton Sári
sumber
1 
perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
eb58
sumber
2
Bisakah Anda menambahkan penjelasan.
Mehdi Bounya
3
Meskipun jawaban ini dapat menyelesaikan pertanyaan, tidak ada penjelasan tentang bagaimana atau mengapa demikian.
samlev
1 

const permutations = array => {
  let permut = [];
  helperFunction(0, array, permut);
  return permut;
};

const helperFunction = (i, array, permut) => {
  if (i === array.length - 1) {
    permut.push(array.slice());
  } else {
    for (let j = i; j < array.length; j++) {
      swapElements(i, j, array);
      helperFunction(i + 1, array, permut);
      swapElements(i, j, array);
    }
  }
};

function swapElements(a, b, array) {
  let temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

console.log(permutations([1, 2, 3]));
Luaskan cuplikan

ASHISH RANJAN
sumber
1

Cukup telat. Masih berjaga-jaga jika ini membantu siapa pun.

function permute(arr) {
  if (arr.length == 1) return arr

  let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i + 1)])
                              .map(v => [d,v].join(''))).flat()

  return res
}

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

Nitish Narang
sumber
1

Saya memiliki celah dalam membuat versi ini yang mencoba untuk menjadi singkat namun dapat dibaca, dan pemrograman murni fungsional.

function stringPermutations ([...input]) {
  if (input.length === 1) return input;

  return input
    .map((thisChar, index) => {
      const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
      return stringPermutations(remainingChars)
        .map(remainder => thisChar + remainder);
    })
    .reduce((acc, cur) => [...acc, ...cur]);
}

Perhatikan bahwa pemformatan argumen mengubah string input menjadi array. Tidak yakin apakah itu terlalu ajaib .. Tidak yakin saya pernah melihatnya di alam liar. Untuk keterbacaan yang nyata, saya mungkin akan melakukannya input = [...input]untuk baris pertama fungsi.

jameslol
sumber
1

Ini adalah implementasi dari algoritma Heap (mirip dengan @ le_m), kecuali itu rekursif.

function permute_kingzee(arr,n=arr.length,out=[]) {
    if(n == 1) {
        return out.push(arr.slice());
    } else {
        for(let i=0; i<n; i++) {
            permute_kingzee(arr,n-1, out);
            let j = ( n % 2 == 0 ) ? i : 0;
            let t = arr[n-1];
            arr[n-1] = arr[j];
            arr[j] = t;
        }
        return out;
    }
}

Sepertinya ini juga lebih cepat: https://jsfiddle.net/3brqzaLe/

Zee
sumber
0

Saya menulis posting untuk mendemonstrasikan bagaimana mengubah array dalam JavaScript. Berikut adalah kode yang melakukan ini.

var count=0;
function permute(pre,cur){ 
    var len=cur.length;
    for(var i=0;i<len;i++){
        var p=clone(pre);
        var c=clone(cur);
        p.push(cur[i]);
        remove(c,cur[i]);
        if(len>1){
            permute(p,c);
        }else{
            print(p);
            count++;
        }
    }
}
function print(arr){
    var len=arr.length;
    for(var i=0;i<len;i++){
        document.write(arr[i]+" ");
    }
    document.write("<br />");
}
function remove(arr,item){
    if(contains(arr,item)){
        var len=arr.length;
        for(var i = len-1; i >= 0; i--){ // STEP 1
            if(arr[i] == item){             // STEP 2
                arr.splice(i,1);              // STEP 3
            }
        }
    }
}
function contains(arr,value){
    for(var i=0;i<arr.length;i++){
        if(arr[i]==value){
            return true;
        }
    }
    return false;
}
function clone(arr){
    var a=new Array();
    var len=arr.length;
    for(var i=0;i<len;i++){
        a.push(arr[i]);
    }
    return a;
}

Telepon saja

permutasi ([], [1,2,3,4])

akan bekerja. Untuk detail tentang cara kerjanya, silakan lihat penjelasan di posting itu.

PixelsTech
sumber
0 
function nPr(xs, r) {
    if (!r) return [];
    return xs.reduce(function(memo, cur, i) {
        var others  = xs.slice(0,i).concat(xs.slice(i+1)),
            perms   = nPr(others, r-1),
            newElms = !perms.length ? [[cur]] :
                      perms.map(function(perm) { return [cur].concat(perm) });
        return memo.concat(newElms);
    }, []);
}
Yunus
sumber