CODEWITHSUNDEEP
algorithmpermutation
user825286
user825286

Reputation:

Python: all possible words (permutations) of fixed length in mini-alphabet

Let's say I have a string like so:

abcdefghijklmnopqrstuvwxyz1234567890!@#$%^&*()-_+={}[]\:;"'?/>.<,`~|€

This is basicly a list of all the characters on my keyboard. How could I get all possible combinations for, let's say, a "word" made up of 8 of these chars? I know there are going to be millions of possibilities.

Cheers!

Upvotes: 4

Views: 8131

Answers (1)

ninjagecko
ninjagecko

Reputation: 91092

Difference between permutations and combinations

You are either looking for a permutation or a combination.

'abc' and 'bac' are different permutations, but they are the same combination {a,b,c}.

Permutations of 'abc': '', 'a', 'b', 'c', 'ab', 'ba', 'ac', 'ca', 'bc', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'

Combinations of 'abc': {}, {'a'}, {'b'}, {'c'}, {'a','b'}, {'b','c'}, {'a','c'}, {'a','b','c'}

In python

Use from itertools import * (since the functions there really should be in the default namespace), or import itertools if you'd like.

If you care about permutations:

permutations(yourString, 8)

If you care about combinations :

combinations(yourString, 8)

In other languages

In other languages, there are simple recursive or iterative algorithms to generate these. See wikipedia or stackoverflow. e.g. http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations

Important note

Do note that the number of permutations is N!, so for example your string would have

  • (69 choose 8) = 8 billion combinations of length 8, and therefore...
  • (69 choose 8) * 8! ~= 3.37 × 10^14 permutations of length 8.

You'll run out of memory if you are storing every permutation. Even if you don't (because you're reducing them), it'll take a long time to run, maybe somewhere between 1-10 days on a modern computer.

Upvotes: 10

Related Questions