efficient permuation algorithm for multiple lists

Question

I have a variable number of lists. Each contains different number of elements.

For instance with four lists,

array1 = {1, 2, 3, 4};
array2 = {a, b, c};
array3 = {X};
array4 = {2.10, 3.5, 1.2, 6.2, 0.3};

I need to find all possible tuples whose ith element is from ith list, e.g. {1,a,X,2.10}, {1,a,X,3.5}, ...

Currently I am using a recursive implementation which has performance issue. Therefore, I want to find a noniterative way that can perform faster.

Any advice? Is there any efficient algorithms (or some pseudo code). Thanks!

Some pseudo code of what I implemented so far:

Recusive version:

vector<size_t> indices; // store current indices of each list except for the last one)

permuation (index, numOfLists) { // always called with permutation(0, numOfLists)
  if (index == numOfLists - 1) {
    for (i = first_elem_of_last_list; i <= last_elem_of_last_list; ++i) {
      foreach(indices.begin(), indices.end(), printElemAtIndex());
      printElemAtIndex(last_list, i);
    }
  }
  else {
    for (i = first_elem_of_ith_list; i <= last_elem_of_ith_list; ++i) {
      update_indices(index, i);
      permutation(index + 1, numOfLists); // recursive call
    }
  }
}

non-recursive version:

vector<size_t> indices; // store current indices of each list except for the last one)
permutation-iterative(index, numOfLists) {
  bool forward = true;
  int curr = 0;

  while (curr >= 0) {
    if (curr < numOfLists - 1){
      if (forward) 
        curr++;
      else {
        if (permutation_of_last_list_is_done) {
          curr--;
        }
        else {
          curr++;
          forward = true;
        }
        if (curr > 0) 
          update_indices();
      }
    }
    else {
      // last list
      for (i = first_elem_of_last_list; i <= last_elem_of_last_list; ++i) {
        foreach(indices.begin(), indices.end(), printElemAtIndex());
        printElemAtIndex(last_list, i);
      }
      curr--;
      forward = false;
    }
  }
}

The complexity of this problem cannot be reduced (as amit points out in his answer). You should do some profiling on your code to determine performance-bottlenecks. Also, how large are you lists in reality? How many of them do you have? — Björn Pollex, Dec 05 '12 at 09:22
I gave an answer, in just 1 minute of time 2-downvotes, my answer was similar to this, saying go for loop... http://stackoverflow.com/questions/72209/recursion-or-iteration — Anoop Vaidya, Dec 05 '12 at 09:25
@AnoopVaidya: I did not downvote, but your answer is claiming "use 4 loops", while the OP explicitly says **variable** number of lists. That doesn't say it cannot be done with loops - but definetly not with your suggested answer. — amit, Dec 05 '12 at 09:33
@RvdK, sorry, I cannot really post the original code, as the data structure is far too complex than necessary. But may some pseudo code (updated in my original post) — Orunner, Dec 05 '12 at 10:20

amit · Answer 1 · 2012-12-05T09:46:38.623

3

There are O(l^n)¹ different such tuples, where l is the size of a list and n is the number of lists.

Thus, generating all of them cannot be done ~~efficiently~~ polynomially.

There might be some local optimizations that can be made - but I doubt swtiching between iterative and (efficient) recursive will do a lot of difference if any, especially if the iterative version is trying to mimic a recursive solution using a stack + loop, which is likely less optimized for this purpose then the hardware stack.

A possible recursive approach is:

printAll(list<list<E>> listOfLists, list<E> sol):
  if (listOfLists.isEmpty()):
      print sol
      return
  list<E> currentList <- listOfLists.removeAndGetFirst()
  for each element e in currentList:
      sol.append(e)
      printAll(listOfLists, sol) //recursively invoking with a "smaller" problem
      sol.removeLast()
  listOfLists.addFirst(currentList)

(1) To be exact, there are l1 * l2 * ... * ln tuples, where li is the size of the ith list. for lists of equal length it decays to l^n.

edited Dec 05 '12 at 09:46

answered Dec 05 '12 at 09:21

amit

175,853
27
231
333

thanks for your answer. From what I noticed through profiling, the iterative implementation may have large overhead. That is my guess and is the reason I started to reimplement this piece of the code. I managed to finish one version but not satisfied with the result. I think, there must be some "text book" and classic algorithm for this type of problems. It would be great, if you could point it out. – Orunner Dec 05 '12 at 09:27
@Orunner: I added the classic recursive approach for the problem. I used something very similar to it when I needed it. Note the complexity is indeed as I mentioned. – amit Dec 05 '12 at 09:33
Of course generating the tuples can be done efficiently, just as it can be done inefficiently. What can't be done is derive an algorithm in a complexity class lower than the complexity of the problem. – High Performance Mark Dec 05 '12 at 09:42
@HighPerformanceMark: In the literature "efficiently" = "polynomially". I meant this terminology when saying "efficiently" in this context. – amit Dec 05 '12 at 09:45
@HighPerformanceMark, thx for your answer. I am not asking an algorithm whose complexity is lower than the complexity of this problem. I am searching one that perform "efficiently". – Orunner Dec 05 '12 at 09:54

efficient permuation algorithm for multiple lists

1 Answers1