2

I need to get permutations, excluding mirrored sequences, i.e. (1, 0, 4) should be included, but (4, 0, 1) should be excluded after. I've came up with the following function but is wondering whether there is simpler solution.

The function skips inverses basing on the fact their last element is the same as the first element of the corresponding sequence, which is already processed given lexicographical order.

def permutations_no_inverse(iterable):    
    """Return the half of permutations, treating mirrored sequences as the same,
    e.g. (0, 1, 2) and (2, 1, 0) are the same.
    Assume itertools.permutations returns tuples
    """

    all_perm = it.permutations(iterable)
    cur_start = None 
    starts_processed = set()
    for perm in all_perm:
        new_start = perm[0] 
        if new_start != cur_start:
            if cur_start != None:
                starts_processed.add(cur_start)
            cur_start = new_start
        if perm[-1] in starts_processed:
            continue
        else:
            yield perm
noname7619
  • 3,370
  • 3
  • 21
  • 26
  • permutation of what please give an input and out value as an example – Sumit Sep 21 '17 at 11:32
  • @Sumit any iterable, looks like – Ry- Sep 21 '17 at 11:33
  • Would `(1,2,3)` and `(1,3,2)` be valid in your case? Do you want to exclude _only the inverses_? – Felk Sep 21 '17 at 11:39
  • @Idle001 No, in general there are no permutations that are palindromes. I agree that "inverse" is highly misleading, and would call them "reversed permutation". – Sven Marnach Sep 21 '17 at 12:58
  • sorry i misunderstood the question i thought the tuple itself includes its inverse – Abr001am Sep 21 '17 at 12:58
  • I think itertools orders the inverses automatically in the last columns, try `list(itertools.permutations([1,0,4]))[:len(list(itertools.permutations([1,0,4])))/2:]` – Abr001am Sep 21 '17 at 13:09
  • @Idle001 This only works correctly if the iterable has two or three elements. For any other number of elements it fails. (Try e.g. one element or four elements.) – Sven Marnach Sep 21 '17 at 14:06

3 Answers3

2

Assuming the entries in iterable are unique and orderable, I would simply compare any two elements of the permutation (e.g. the first and last one), and only include those permutations where the first element is less or equal than the last element. This way, you don't need to store what you have already seen, and you don't care in what order itertools.permutations() returns the permutations.

Example code:

def permutations_no_inverse(iterable):
    for p in itertools.permutations(iterable):
        if p[0] <= p[-1]:
            yield p
Ry-
  • 218,210
  • 55
  • 464
  • 476
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
0

Your question has explicited stated ...wondering whether there is simpler solution, i think the below one is simple enough:

def permutations_no_inverse(iterable):
    found_items = []
    for p in it.permutations(iterable):
        if p not in found_items:
            found_items.extend([p, p[::-1]])
        else:
            yield p
BPL
  • 9,632
  • 9
  • 59
  • 117
  • This approach has quadratic runtime, since scanning the list takes linear time. If the elements in `iterable` are hashable, you can use a set instead of a list to get linear runtime. – Sven Marnach Sep 21 '17 at 13:05
  • @SvenMarnach The op hasn't stated elements of iterables would be hashable so i can't assume that. Also, your comment is talking about performance when my answer starts clarifying some facts about simplicity, otherwise i wouldn't have used itertools.permutations in the first place and coding a custom function filtering in place. In any case, thanks for a good remark ;) – BPL Sep 21 '17 at 13:24
  • You are always making assumptions; the important thing is to state them. Your code assumes that the iterable has more than one element (for only one element it returns an empty iterable), that the elements in the iterable are unique (otherwise it may return duplicates), and that the elements support `__eq__()` (which holds for almost everything, but still an assumption). – Sven Marnach Sep 21 '17 at 14:12
0

Based on the fact that python delays the reversed tuple-orderings all for the latest columns, we could envisage the permutations set as a uniform matrix, then divide it diagonally, to get the unmirrored part of the matrix.

k=[1,  2, 3,4]
l=itertools.permutations(k)
a=list(l)
b=np.array(a).reshape((len(k),len(a)/len(k),len(k)))
neat_list=np.flipud(b)[np.tril_indices(len(k))]

This should be effective with all array lengths I guess ....

With k=[1,2,3,4,5,6]

This prints

array([
   [6, 1, 2, 3, 4, 5],
   [5, 1, 2, 3, 4, 6],
   [5, 1, 2, 3, 6, 4],
   [4, 1, 2, 3, 5, 6],
   [4, 1, 2, 3, 6, 5],
   [4, 1, 2, 5, 3, 6],
   [3, 1, 2, 4, 5, 6],
   [3, 1, 2, 4, 6, 5],
   [3, 1, 2, 5, 4, 6],
   [3, 1, 2, 5, 6, 4],
   [2, 1, 3, 4, 5, 6],
   [2, 1, 3, 4, 6, 5],
   [2, 1, 3, 5, 4, 6],
   [2, 1, 3, 5, 6, 4],
   [2, 1, 3, 6, 4, 5],
   [1, 2, 3, 4, 5, 6],
   [1, 2, 3, 4, 6, 5],
   [1, 2, 3, 5, 4, 6],
   [1, 2, 3, 5, 6, 4],
   [1, 2, 3, 6, 4, 5],
   [1, 2, 3, 6, 5, 4]])

I tried : 

test=[list(g) for g in neat_list]
any([(u[::-1] in test) for u in test])

And this outputs false which means no occurence of reversed arrays there.

Abr001am
  • 571
  • 6
  • 19
  • The mere fact that no reversed permutations occur in the list does not make this solution correct; the empty list would satisfy this property. For a six-element list, the result should contain 360 permutations. Your code only gives 21. An example of a missing permutation is `1 3 2 4 5 6`. – Sven Marnach Sep 21 '17 at 18:23
  • @SvenMarnach it's because i pulled the upper side of the diagonal, if i choose the lower, it would print all these sub-arrays reversed, which means a reversed [6 5 4 3 2 1] amongst – Abr001am Sep 21 '17 at 18:24
  • @SvenMarnach i agree there is a mistake in segmentation but this doesn't abort this theory, I'm working on it – Abr001am Sep 21 '17 at 18:55
  • Yeah, it is _possible_ to make something similar work. However, it's not just a "diagonal" in the usual sense, since the matrix you are dealing with is rectangular. It's just not worth the trouble, given that there is the dead simple solution given in my answer. – Sven Marnach Sep 21 '17 at 19:54
  • @SvenMarnach I agree with you, this answer is partially wrong, a toddlerstep into linear solution, but all the triangular slice of the matrix satisfies the condition, while there is more solutions outside the diagonal I still fail to locate ! – Abr001am Sep 22 '17 at 00:12
  • Where does the quotation come from ? – noname7619 Sep 24 '17 at 11:44
  • @VladimirLenin the basis is obviously clear, [you can see the initiative is already opened](https://stackoverflow.com/a/960686/4571206), and I'm not gonna take deep researches since the question exists already and not a new thing. – Abr001am Sep 24 '17 at 12:08