枚舉序列的算法

假設我們有標籤的序列，例如以下

E1 B1 B2 E2 B3 E3

指標沒有任何意義，我用他們爲了不同的B的和E的區分。

該任務列舉了可能構造的BE對的所有可能序列。

例如從上面的例子我可以構建

B1 E2 

B1 E3 

B1 E2 B3 E3 

B2 E2 

B2 E3 

B2 E2 B3 E3 

B3 E3

希望我發現所有的人，所述序列（對數）的長度不限當然。對總是B E，其中B開始，E結束。

問題是我不能拿出一些通用的東西。

來源

2014-04-03 user16168

我想通過創建兩個新的列表開始;一個與B的，另一個與E的。在這之後找出算法應該是微不足道的。 –

關閉@ RobertHarvey的評論，您可以通過過濾現有的列表來創建列表。第一個字符匹配。 –

認爲這應該做的伎倆。這當然沒有優化。

var labels = ['E1', 'B1', 'B2', 'E2', 'B3', 'E3']; 
var results = []; 
var temp_results = []; 
var i, j, index, new_item; 

// Utility function to add an array inside an other array if it isn't in it yet. 
function pushIfNotExists(container, insert) { 
    var found = false; 
    var i, different; 
    container.forEach(function(item) { 
    if (item.length === insert.length) { 
     different = false; 
     for (i = 0; i < item.length; i++) { 
     if (item[i] !== insert[i]) { 
      different = true; 
     } 
     } 
     if (!different) { 
     found = true; 
     } 
    } 
    }); 

    if (!found) { 
    container.push(insert); 
    } 
} 

// This loops makes the basic (2 labels) sequences. 
for (i = 0; i < labels.length; i++) { 
    if (labels[i].charAt(0) === 'B') { 
    for (var j = i + 1; j < labels.length; j++) { 
     if (labels[j].charAt(0) === 'E') { 
     temp_results.push([labels[i], labels[j]]); 
     } 
    } 
    } 
} 

// This loops combines the sequences 
while (temp_results.length > results.length) { 
    results = temp_results.slice(0); 
    for (i = 0; i < results.length; i++) { 
    index = labels.indexOf(results[i][results[i].length - 1]); 
    for (j = index + 1; j < results.length; j++) { 
     if (labels.indexOf(results[j][0]) > index) { 
     new_item = results[i].concat(results[j]); 
     if (temp_results.indexOf(new_item) === -1) { 
      pushIfNotExists(temp_results, new_item); 
     } 
     } 
    } 
    } 
} 

console.log(results);

來源

2014-04-03 23:12:34 ploutch

一些（不完全）的想法...

E1 B1 B2 E2 B3 E3 
pos 1 2 3 4 5 6 

posB = indices of B // 2, 3, 5 
posE = indices of E // 1, 4, 6 

output = {}  

append_list_of_len_2(): 
    for i = 1 to len(posB): 
     j = first elem in posE greater than i 
     for(; j < len(posE); j++): 
      output.append({i, j})

來源

2014-04-03 23:19:30 Arun

枚舉序列的算法

回答

相關問題