CODEWITHSUNDEEP
algorithmcombinatorics
weisk
weisk

Reputation: 2540

All possible combinations of a given string

I need to find all possible combinations of a given string, from a minimum length to a maximum length.

interface allCombos(string: String, min: Number, max:Number): Array {}

So if my input string is ‘abcde’, and my minimum length is 3, I want the result to be:

For length 3:

[‘abc’, ‘abd’, ‘abe’, ‘acd’, ..., ‘bcd’, ‘bce’, ..., ‘eda’, ...]

Concatenated with length 4:

[‘abcd’, ‘abdc’, ‘acdb’, ‘acbd’, …etc]

Concatenated with all possible combinations with length up to the max parameter. Which shouldn't be higher than the input word length.

I started thinking that all possible combinations would be ∑(3! + 4! + … + n!). But then I saw I'm wrong because for every length subset, there are many combinations for the whole world (for example 3-length combinations of a 6 letter string).

Can the community help me with this problem?

The solution can either be in JavaScript, Python or even pseudo code.

Edit

For knowledge's sake. Could anyone answer me, the formula that describes the result size in this case? I know its not ∑(3! + 4! + … + n!).

Upvotes: 3

Views: 2153

Answers (4)

jack6e
jack6e

Reputation: 1522

Others showed you some nice options for combinations/permutations, but I think your full expected output is something like this:

from itertools import combinations

def allCombos(str, min_length, max_length):
    str_combinations = []
    for length in range(min_length, max_length):
        combinations = [''.join(c) for c in combinations(str, length)]
        str_combinations.append(combinations)
    return str_combinations

Upvotes: 1

guest271314
guest271314

Reputation: 1

[Edit]: For knowledge's sake. Could anyone answer me, the formula that describes the result size in this case? I know its not ∑(3! + 4! + … + n!).

Below find three mathematical approaches which provide the same ultimate result using JavaScript. For further descriptions of the procedure see

further items of interest within the subject matter

const n = 4;

{
  console.log("multiplication in loop:\n");
  let l = 1,
    k;

  for (let i = k = n; l < i; k *= l++);

  console.log({
    [`${n}!`]: k
  });
}

{
  console.log("single multiplication 4 * 3 * 2 * 1:\n");
  console.log({
    [`${n}!`]: 4 * 3 * 2 * 1
  });

}

{
  console.log("multiplication in steps:\n");
  
  let curr = n;
  
  let acc = {};
  
  acc[`${curr} * ${curr - 1}`] = curr * --curr;
  
  console.log(acc);
  
  acc[`${Object.keys(acc).pop()} * ${--curr}`] = curr * +acc[Object.keys(acc).pop()];
  
  console.log(acc);
  
  acc[`${Object.keys(acc).pop()} * ${--curr}`] = curr * +acc[Object.keys(acc).pop()];
  
  console.log(acc);

}

Upvotes: 1

Cleb
Cleb

Reputation: 25997

You can use itertools.combinations for this:

from itertools import combinations

["".join(li) for li in combinations('abcde', 3)]

This will give

['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde']

Brief explanation:

list(combinations('abcde', 3))

will give

[('a', 'b', 'c'),
 ('a', 'b', 'd'),
 ('a', 'b', 'e'),
 ('a', 'c', 'd'),
 ('a', 'c', 'e'),
 ('a', 'd', 'e'),
 ('b', 'c', 'd'),
 ('b', 'c', 'e'),
 ('b', 'd', 'e'),
 ('c', 'd', 'e')]

so all combinations of three of your letters. You can join the individual tuples then in a list comprehension.

You can then of course easily put this in a loop if you like:

min_length = 3
max_length = 5

res = {str(i): ["".join(li) for li in combinations('abcde', i)] for i in range(min_length, max_length + 1)}

This gives

{'3': ['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde'],
 '4': ['abcd', 'abce', 'abde', 'acde', 'bcde'],
 '5': ['abcde']}

If you want to have it in a single list:

import numpy as np
final_list = np.concatenate(res.values())

which yields

array(['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde',
       'cde', 'abcde', 'abcd', 'abce', 'abde', 'acde', 'bcde'],
      dtype='|S5')

Upvotes: 3

costrouc
costrouc

Reputation: 3175

I am happy to introduce you to the wonderful python standard library itertools! You will want to use the combinations function. What is awesome about this library is that it solves almost all combinatoric loop problems.

 import itertools

 min_length = 2
 max_length = 5

 s = 'ABCDEF'
 for i in range(min_length, max_length):
     print('length', i, 'cominations')
     print([_ for _ in itertools.combinations(s, i)])

Upvotes: 1

Related Questions