CODEWITHSUNDEEP
node.jsalgorithmsequence
user16168
user16168

Reputation: 655

algorithm enumerating sequences

I have an algorithmic problem.

Assume we have a sequence of labels like following

E1 B1 B2 E2 B3 E3

indexes don't have any meaning, I used them in order to distinguish between different B's and E's.

The task is enumerate all possible sequence of pairs BE that could be construct.

for example from the above example I can construct

B1 E2

B1 E3

B1 E2 B3 E3

B2 E2

B2 E3

B2 E2 B3 E3

B3 E3

I hope I found all of them, the length of the sequence (the number of pairs) is not limited of course. Pairs are always B E, where B for begin, E for end.

The problem is I cannot come up with something generic.

Upvotes: 0

Views: 68

Answers (2)

Arun
Arun

Reputation: 20383

Some (incomplete) thoughts...

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

Upvotes: 0

ploutch
ploutch

Reputation: 1214

think this should do the trick. It's certainly not optimized though.

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

Upvotes: 1

Related Questions