How can i create a permutation with a limit on specific characters efficently?

Question

To give you an idea of what i'm talking about. This is the code i have now:

chrs = 'ABCDEF1234567890'
with open('two.txt', 'w') as two:
    for xs in itertools.product(chrs, repeat=10):
        h = sum(x.isalpha() for x in xs)
        if h == 2: two.write(''.join(xs) + '\n')

Unfortunately this literally takes days as it creates every possible combination, most of which do not match.

EDIT: To clarify, i need a way of finding all possible combinations of the variable chrs where there are only two letters ('ABCDEF'). Without creating an entire list of all combinations and checking each one. I need to create just the ones that have two letters in them.

To go even further:

'AA12345678' = Good
'1234A123A4' = Good
'AAA1234567' = Bad
'A123456789' = Bad

I really don't know how much more i can explain just 5 lines of python code.

What? What is `h`, just the `repeat` for `product`? *"most of which do not match"* - do not match **what?** — jonrsharpe, May 18 '15 at 11:05
h is the count of letters in the string. Letters being ABCDEF. For the not matching part, see the comparison where it checks the count to see if it's equal to two. — Jai-Kai, May 18 '15 at 11:19
Not voting to close: It is *entirely* clear what OP is asking for. Just because the variables are badly named doesn't mean the question is ill-formed. — Kevin, May 18 '15 at 13:59

score 2 · Accepted Answer · edited May 23 '17 at 12:14

This is based on stars and bars rather than combinations and permutations.

Start with a standard stars and bars algorithm, a refinement of my previous work:

def stars_and_bars(star='*', bar='|', star_count=8, bar_count=2):
    if star_count == 0:
        yield (bar,) * bar_count
        return
    if bar_count == 0:
        yield (star,) * star_count
        return
    for left in range(star_count + 1):
        right = star_count - left
        assert right >= 0
        assert left + right == star_count
        for partial in stars_and_bars(star, bar, left, bar_count - 1):
            yield partial + (bar,) + (star,) * right

Verify that it works:

>>> sandb = stars_and_bars(star_count=3, bar_count=2)
>>> for result in sandb:
...     print(''.join(result))
... 
||***
|*|**
*||**
|**|*
*|*|*
**||*
|***|
*|**|
**|*|
***||

As you can see, this produces each possible arrangement of stars and bars. With 8 stars and two bars, we can use this to find all possible arrangements of numbers and letters. We'll then pass that to itertools.product():

def combos():
    letters = 'ABCDEF'
    numbers = '1234567890'
    argument_combos = stars_and_bars(numbers, letters)
    for args in argument_combos:
        yield from itertools.product(*args)

The result will be exactly what OP asked for.

score 0 · Answer 2 · answered May 18 '15 at 13:44

Well it's just the hexadecimal numbers from 0x0 to 0x10000000000. Unfortunately, that's ~1.75e13 in decimal, so if each char is 1 byte and each string is 10 chars, without filtering your two.txt would be 175TB in size.

Once you think of it like that though, there should be some way to quickly cull large swathes of the list with a few simple modulus operations, which would be the avenue I would go down.

score 0 · Answer 3 · edited May 23 '17 at 12:30

I've upvoted the second answer by Kevin but I'm still under the impression that his stars_and_bars implementation is a little overdone... here it is my take at it

OH MY, copy&paste mistakes... one parentesis moved down one line...

$ cat starbar.py
from itertools import combinations as _ic_
def sb(s, ns, b, nb):
    l = list(range(nb+ns) ---------------V
    return ([b if i in k else s for i in l)]for k in _ic_(l, nb))

now this is the correct version

$ cat starbar.py
from itertools import combinations as _ic_
def sb(s, ns, b, nb):
    l = list(range(nb+ns))
    return ([b if i in k else s for i in l] for k in _ic_(l, nb))

or, if you prefer verbose names,

from itertools import combinations
def stars_and_bars(star, number_of_stars, bar, number_of_bars):
    possible_positions = list(range(number_of_bars + number_of_stars))
    return ([bar if i in combination else star for i in l]
            for combination in combinations(possible_positions, number_of_bars))

and how it works? to fix the ideas, say ns, nb = 2, 3 and look at what is done by itertools.combination

>>> list(itertools.combinations(range(ns+nb),nb))
[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

you have an iterable with all the possible ordered choices of 3 different numbers in [0,1,2,3,4] and at this point it's easy to return a list containing the right sequence of stars and bars

>>> from starbar import sb
>>> for s_b in sb('*',2, '|',3): print ''.join(s_b)
...
|||**
||*|*
||**|
|*||*
|*|*|
|**||
*|||*
*||*|
*|*||
**|||
>>>

I can understand my implementation. I can't understand yours, especially since it gives me a syntax error under 3.4. — Kevin, May 28 '15 at 13:15
There was a mistake in the code I had posted, a parenthesis slipped one line down... I've it corrected now, I've also given an explanation and an example — gboffi, May 28 '15 at 19:08
I still don't really understand how you're achieving that result. Maybe if you used whole words for your variable name it would make more sense to me. — Kevin, May 28 '15 at 19:23

How can i create a permutation with a limit on specific characters efficently?

3 Answers3