6

I'm trying to create a recursive version of the following nested loops and to get the same results as the reference code. The example is below.

This is a version on Codepen http://codepen.io/anon/pen/XbQMLv

(The intent of the code is to output only unique combinations of integers from the indexes.)

Original code and output:

var len = 4;

for (var a = 0; a < len; a++) {
  for (var b = a + 1; b < len; b++) {
    for (var c = b + 1; c < len; c++) {
      console.log(a, b, c);
    }
  }
}
// Outputs:
// 0 1 2
// 0 1 3
// 0 2 3
// 1 2 3

Recursive code and output:

var len = 4;
var end = 3;
var data = [];

var loop = function (index) {
  if (index === end) {
    console.log(data);
    return;
  }
  for (var i = index; i < len; i++) {
    data[index] = i;
    loop(i + 1);
  }
}

loop(0);
// Outputs:
// [ 0, 1, 2 ]
// [ 0, 2, 3 ]
// [ 1, 3, 2 ]
// [ 2, 3, 3 ]

Not sure what I'm missing here.

Improve this question
7
  • How are you using end with the loops? Commented Aug 13, 2015 at 4:48
  • If you want unique combinations, do you mean you want permutations of that array? Commented Aug 13, 2015 at 4:49
  • @elclanrs I'm trying to get the recursive version to have the same output as the original reference version. Commented Aug 13, 2015 at 4:52
  • What is the point of the array then? If you can just do var len = 4; for (var a = 0; a < len; a++) ... Commented Aug 13, 2015 at 4:55
  • oh right right right. Ignore the array. I'll be reading the values of the array later. Its only used for the length in the question. Sorry about the confusion. Commented Aug 13, 2015 at 4:56

4 Answers 4

Reset to default
4

You have a single little error in your code:

You call a recursive function from your i + 1, but not your index + 1.
It causes index to be equal not current array index but it's value.

For example, when you passed [0, 1, 2], your data now is [0, 1] and you are about to insert 3, you call loop(3 + 1), index 4 goes out of an array range. if (index === end) condition fails and it doesn't output. for (var i = index; i < len; i++) loop fails as well, and everything is going wrong.

It should be:

var len = 4;
var end = 3;
var data = [];

var loop = function (index) {
  if (index === end) {
    console.log(data);
    return;
  }
  for (var i = index; i < len; i++) {
    data[index] = i;
    loop(index + 1); // <--- HERE
  }
}

loop(0);

Here is the working JSFiddle demo.

Update:

Oh, now I see. You need a[i] > a[i-1] condition to be true for all combinations. Just add a start variable which will save the last inserted value in order to comply with this rule.

var len = 4;
var end = 3;
var data = [];

var loop = function (start, index) {
  if (index === end) {
    document.body.innerHTML += "<br/>" + data;
    return;
  }
  for (var i = start; i < len; i++) { // We start from 'start' (the last value + 1)
    data[index] = i;
    loop(i + 1, index + 1); // Here, we pass the last inserted value + 1
  }
}

loop(0, 0); // At beginning, we start from 0

Updated JSFiddle demo with passing argument.

You can check the previous value instead of passing a value as an argument if it looks wrong for you. Condition will be like "if it is a first number, start from 0; else - start from the next number after the previous one".

var start = (index === 0 ? 0 : data[index-1] + 1);

Updated JSFiddle demo with calculating start.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you, but this isn't the expected outcome. Your version is iterating through all possible versions. I'm trying to match the output of the nested for loops in the original example.
@Geuis Updated it again :)
Holy crap thanks! Such a subtle bug that I kept missing. I was using 'index' as start and had been thinking that since it got incremented on every call to loop() that should suffice. I totally missed that since its being incremented in the loop it was throwing off the indexes for updating data!
3

There are a couple of errors; you are recursing starting from i+1 instead of index+1 and you are counting from index instead of counting from data[index-1]+1.

The corrected version is:

var len = 4;
var end = 3;
var data = [];

var loop = function (index) {
  if (index === end) {
    console.log(data);
    return;
  }
  for (var i = (index==0 ? 0 : data[index-1]+1); i < len; i++) {
    data[index] = i;
    loop(index + 1);
  }
}
Improve this answer

Comments

2

As you are having three for loops one inside another, you have to pass 2 arguments for recursion function.

var len = 4;
var end = 3;
var data = [];

var loop = function(start, index) {
  if (index === end) {
    console.log(data);
    return;
  }
  for (var i = start; i < len; i++) {
    data[index] = i;
    loop(i + 1, index + 1); //Pass as like a+1 & b+1
  }
}

loop(0, 0);

Improve this answer

Comments

1

Output the exact expected result.

var len = 4;
var end = 3;
var data = [];

var loop = function(i) {
  if(data.length === end) {
    // console.log(data); -> Wont work in snippet
    
    // Snippet workaround
    document.getElementsByTagName('body')[0].innerHTML += data.join(',') + '<br/>';
    return;
  }

  if(i >= len)
    return;

  data.push(i);
  loop(i + 1);

  data.pop();
  loop(i + 1);
};

loop(0);

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.