兩個數組，其中數組x中的項可以在數組y中，但反之亦然，測試所有排列

我編寫的一個小型應用程序允許用戶將各種項添加到兩個數組。有些邏輯根據每個數組的內容計算一個數字。兩個數組，其中數組x中的項可以在數組y中，但反之亦然，測試所有排列

數組x中的任何項都可以放入數組y中，然後再返回。屬於數組y的項目永遠不能移動（除非它們從數組x移動）。

用戶可以使用簡單的javascript ui將這些項目移動到兩個列表中。爲了使事情更簡單，我原本做了一個幼稚的腳本：

將項目從a移到y。
使用此'可能性'執行某些邏輯
如果結果小於以前，請在x中保留x。
如果不是，則x保留在x中。
移至x中的下一項並重復。

我知道這是無效的。我已經閱讀並且被告知使用按位數學來記住可能性或'排列組合'，但在這個階段我正在努力解決這個特定問題。

如果任何人能夠解釋（僞代碼是好的）什麼是最好的方式來實現以下我將非常感激。

數組x = [100,200,300,400,500] 量陣列y = [50150350900]

通過這兩個陣列，用於從X的每個值，按該值和所有其他值的每一種組合，從x轉換成量陣列y。對於每一個我將執行一些邏輯（即測試結果並將這個'置換'存儲在一個數組中（兩個數組的對象代表x和y）。我預計這對於大數組非常昂貴，可能會重複很多。組合我覺得我幾乎沒有，但在這個最後階段失去了

對不起，長的解釋，並在此先感謝

來源

2013-03-26 Niechea

你不是真的在尋找所有[排列組合（http://en.wikipedia.org/wiki/Permutation），是嗎？你在尋找你想迭代的[power set]（http://en.wikipedia.org/wiki/Power_set）嗎？或者你甚至需要解決某種[揹包問題]（http://en.wikipedia.org/wiki/Knapsack_problem）？ – Bergi 2013-03-26 23:00:08

我明白你揹包問題的含義，但我認爲我的問題並不複雜。請原諒我可怕的數學知識，但是，是的，權力集合是我想要達成的目標，即獲得x的所有組合。 x [0,2] + y [5,6] = z [5,6]，z [5,6,0]，z [5,6,2]，z [5,6,2,0]，（not）！[5,6,0,2] – Niechea 2013-03-26 23:17:32

因此，獲取y的所有可能的子集（作爲數組，項目的順序與y中的順序相同），並將它們中的每一個與x相加？這很簡單:-) – Bergi 2013-03-26 23:20:56

使用此爲創建power setx的：！

function power(x, y) { 
    var r = [y || []], // an empty set/array as fallback 
     l = 1; 
    for (var i=0; i<x.length; l=1<<++i) // OK, l is just r[i].length, but this looks nicer :) 
     for (var j=0; j<l; j++) { 
      r.push(r[j].slice(0)); // copy 
      r[j].push(x[i]); 
     } 
    return r; 
}

用法：

> power([0,2], [5,6]) 
[[5,6,0,2], [5,6,2], [5,6,0], [5,6]]

有人告訴我做這個使用逐數學記的可能性或「置換」，但我竭力在這個階段，讓我解決這個特定問題的頭。

這將是迭代2 ^Ñ（對於長度爲n的陣列），使用單位來確定的項是否應當被包括在子集中。例如用於陣列[A，B]：

i binary included in set 
----------------------------- 
0 00  {  } 
1 01  { b } 
2 10  { a } 
3 11  { a, b }

我們可以使用在JS bitwise operators爲陣列，最多31項（這應該是足夠了）。

function power(x, y) { 
    var l = Math.pow(2, x.length), 
     r = new Array(l); 
    for (var i=0; i<l; i++) { 
     var sub = y ? y.slice(0) : []; 
     for (var j=0; j<x.length; j++) 
      // if the jth bit from the right is set in i 
      if (i & Math.pow(2,j)) // Math.pow(2,j) === 1<<j 
       sub.push(x[j]); 
     r[i] = sub; 
    } 
    return r; 
}

來源

2013-03-26 23:59:23 Bergi

謝謝，這正是我所尋找的：D – Niechea 2013-03-27 00:36:08

兩個數組，其中數組x中的項可以在數組y中，但反之亦然，測試所有排列

回答

相關問題