2
\$\begingroup\$

I'm looking for combinations, not permutations, and have found some really great examples ranging from using flatMap such as https://stackoverflow.com/a/54329187/669843

The result of ['a', 'b', 'c'] would be an array of arrays of 3 (a, b, and c). The result I'm looking for would also contain arrays of length 1 and 2.

Example:

['a']
['b']
['c']
['a', 'b']
['a', 'b', 'c']
['a', 'c']
...

I'm accomplishing the results with something like this but this seems extraordinarily awful and requires de-duplication.

for(let i = 0; tci < combo.length; tci++) {
  let newcombo = [allitems[item]].concat(combo.slice(tci, combo.length));
  ...
  push newcombo;
\$\endgroup\$
3
  • \$\begingroup\$ Wonder why this off topic? It has running code and wonders how to make it better? \$\endgroup\$ Feb 13, 2020 at 19:59
  • \$\begingroup\$ @charles, because the code shown for review is a couple of lines with absolutely no context (there's stuff obviously missing in the mysterious ... region, and variables combo, item and tci appear out of nowhere). There's clearly quite a bit that's missing before this function is reviewable. \$\endgroup\$ Feb 14, 2020 at 8:51
  • \$\begingroup\$ I understand! Thanks. I was trying to be brief but I'm going to give it a few passes and resubmit later, @TobySpeight \$\endgroup\$ Feb 14, 2020 at 20:57

1 Answer 1

-2
\$\begingroup\$

You can write this better. The best way to explain it is to see the code example in Python's itertools module:

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

This generates the combinations of length 'r' efficiently using counting. You can create all combinations by either adding length-1 'nulls' to the pool or just iterating over the lengths.

Combination generation is a bit hard to grok, and really you should step through this example until you get it. It's a variation on the idea of manually counting used throughout many algorithms.

The base idea for combinations('ABCD', 2) is to start with 'AB' (first yield), increment the last letter 'AC' then 'AD' with the for j loop doing nothing, on the next loop i will be the index 0, so 'A' -> 'B' and the second resets to one more than the first character and you yield 'BC'.

Trace the code. Keep hacking! Keep notes.

\$\endgroup\$
5
  • \$\begingroup\$ That's a pretty good example. It definitely can be better, but one of the points I was trying to make was a more graceful way of doing it. In the itertools example you have a very nice generator. Is a JavaScript generator a suggestion? I really want to avoid the while with a for, etc, which is where I am now. \$\endgroup\$ Feb 10, 2020 at 3:47
  • 1
    \$\begingroup\$ A simpler way to iterate all combinations of all lengths is to see that each element may be either absent or present. There's a natural mapping to binary numbers of length n (start from 0 or 1 depending on whether you want to include the empty set as a result). \$\endgroup\$ Feb 10, 2020 at 8:48
  • 2
    \$\begingroup\$ The question is tagged javascript. The consensus is that answers should use the same language as the code in the question. Also Please note, questions involving stub code are off-topic on this site. If OP edits their post to address the problem and make their post on-topic, they make your answer moot. It is advised not to answer such questions. Protip: There are many on-topic questions to answer; you'll make more reputation faster if you review code in on-topic questions. \$\endgroup\$ Feb 10, 2020 at 23:17
  • \$\begingroup\$ Sigh. Everytime I write an answer the 'this how we should do it here' folks come out. I only rarely write answers now. \$\endgroup\$ Feb 13, 2020 at 19:57
  • \$\begingroup\$ @TobySpeight Very nice insight! So just mapping the range of numbers pow(2, combo.length) through string(2) for binary and tuples of matching number. Very slick. \$\endgroup\$ Feb 14, 2020 at 3:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.