2

I'm trying to write a function that does the following:

> partitions([a,b,c,d])

< [
  [[a,b],[c,d]],
  [[a,c],[b,d]],
  [[a,d],[b,c]]
  ]

i.e. it finds all partitions of size 2.

Currently I'm trying to do it recursively: at each call generate a list of pairs, and for each pair generated, call the method again on the list with that pair removed. This works, but it generates duplicates. Removing the duplicates requires comparing each element in the partitions generated, this is super slow.

I was wondering if there is a smarter way to do this.

zzz
  • 233
  • 3
  • 8
  • Another way that I think this can be done is by generating all permutations that are unique up to a cyclic shift, then just group the results by index. Is there a efficient method for generating all permutations that are not cyclically related (without having to by brute force removing the cyclic permutations)? – zzz Jul 21 '14 at 17:28

2 Answers2

2

Just get combinations of all the items and filter out all that is not needed, like this

function getTwoCombinations(array) {
    var i, j, result = [];
    for (i = 0; i < array.length; i += 1) {
        for (j = i + 1; j < array.length; j += 1) {
            result.push([array[i], array[j]]);
        }
    }
    return result;
}

var result = getTwoCombinations(getTwoCombinations(["a", "b", "c", "d"])).
    filter(function(items) {
        return items[0].every(function(item) {
            return !(items[1].indexOf(item) + 1);
        });
    });

console.log(result);

Output

[ [ [ 'a', 'b' ], [ 'c', 'd' ] ],
  [ [ 'a', 'c' ], [ 'b', 'd' ] ],
  [ [ 'a', 'd' ], [ 'b', 'c' ] ] ]
thefourtheye
  • 233,700
  • 52
  • 457
  • 497
  • Thanks this is very straightforward. Somehow I convinced myself that doing this would be slow, but that is clearly not the case, so thank you. – zzz Jul 21 '14 at 17:42
  • Problem though, seems this doesn't work for anything with more than 4 elements. – zzz Jul 21 '14 at 18:16
  • We need to generalize getTwoCombinations to one which constructs arbitrary number of pairings, getNCombinations, and replace getTwoCombinations(getTwoCombinations(...)) with getNCombinations(getTwoCombinations(...),N), where N is easily determined from the list size. – zzz Jul 21 '14 at 18:28
0

A good strategy is:

From first to last

  1. Lock one element (first element)

    1.1 Iterate over the next elements (second until the end) and create the pairs

  2. Lock the next element (second element)

    2.1 Iterate over the next elements (third until the end) and create the pairs

3... repeat until the last but one element

A visual help:

[a, ]
  [a, b]
  [a, c]
  [a, d]

[b, ]
  [b, c]
  [b, d]

[c, ]
  [c, d]
Luizgrs
  • 4,765
  • 1
  • 22
  • 28
  • That just generates all combinations, not partitions, no? – zzz Jul 21 '14 at 17:35
  • isn't it correct to say that if the list is ordered it will also returns the partitions? – Luizgrs Jul 21 '14 at 17:38
  • ordered by what? of course the partitions would be subsets of these things that you generate here, but is it obvious how to group them? – zzz Jul 21 '14 at 17:40