permutations with restrictions on python

Question

I want to create all possible sequence of numbers with 10 digits by using numbers 0 to 9 . Each digit should be used only once like:

5 2 8 7 3 0 6 1 9 4 and 5 0 6 2 7 8 3 1 9 4.

So there are P(10,10) = 3 628 800 possible combinations out there. However there are three rules about the ordering of elements:

2 > 8 > 3 > 9 > 4 (rule 1) and 5 > 9 > 4 (rule 2) and 2 > 8 > 1 (rule 3). Here > sign means left operand should be on a higher significance digit (meaning closer to the left). Unspecified numbers in the rules which are 0 6 7 could be used anywhere on the combination.

So I have this idea of having a list of all possible combinations and then applying rules one by one and discard the sequences that do not follow. However, after some thoughts, found out that I can further assess the precise position for some digits, lets say 2. Looking at 2,8,3,9,4 (rule 1), there should be at least 4 elements on the rightside of 2--> (8,3,9,4). This makes 2 could be assigned to digits D(1,2,3,4,5,6) (1 is MSB and 10 is LSB). Further investigating 2,8,1 (rule 3) 1 should also be on the right side of 2 that makes 2 could be assigned to D(1,2,3,4,5). There are no further simplifications I figured out, and that's it I guess.

So what kind of approach might work here? I don't know even if the brute-force approach I suggest is feasible yet have to check it but I'm looking for a neater pythonic way to implement this.

P.S. An idea is that we can split rules like

(2>8),(2>3),(2>9),(2>4)

(8>3),(8>9),(8>4)

(3>9),(3>4)

(9>4) for rule 1. But it still looks like a brute-force to me.

Alright, then the answers provided work (let us know if you aren't happy w them). — zabop, Jul 03 '20 at 20:15

score 2 · Accepted Answer · answered Jul 03 '20 at 19:18

2

Easy, you can use itertools.permutations(), and as it generates tuples, we check to see each tuple meets the rules:

from itertools import permutations

for t in permutations(range(10), 10):
    if t.index(2) < t.index(8) < t.index(3) < t.index(9) < t.index(4) and t.index(5) < t.index(9) < t.index(4) and t.index(2) < t.index(8) < t.index(1):
        print(t)

answered Jul 03 '20 at 19:18

Red

26,798
7
36
58

Is `permutations(range(10),10)` generated and then looped through, or it is generated as the loop progresses? – zabop Jul 03 '20 at 19:29
It is generated as the loop progresses. – Red Jul 03 '20 at 19:30
1

This works and I'm shocked after figuring out saving 3.6 m elements into a list only takes mere seconds. – colt.exe Jul 03 '20 at 20:27

score -1 · Answer 2 · answered Jul 03 '20 at 19:17

For the brute force method & for rule1 and rule2, you can do this:

import itertools
allpermutations = list(itertools.permutations([x for x in range(10)]))

def rule1(seq):
    return seq.index(2) < seq.index(8) and seq.index(8) < seq.index(3) and seq.index(3) < seq.index(9) and seq.index(9) < seq.index(4)

def rule2(seq):
    return seq.index(5) < seq.index(9) and seq.index(9) < seq.index(4)

result = [eachsequence for eachsequence in allpermutations if rule1(eachsequence) and rule2(eachsequence)]

(Similarly for rule3.)

For itertools usage, see this, for the .index() method, this.

This is not efficient. It writes *all* possible permutations into memory, when don't need a good fraction of them. — Red, Jul 03 '20 at 19:22

permutations with restrictions on python

2 Answers2