A permutation on permutations 
Author Message
 A permutation on permutations

Was able to find nice stuff on the python-list archives
as to list permutations, list reversal, and removing
duplicates from lists.

My problem is to combine them.

I am feeding control points to a curve function, and
want all permutations that result in unique curves.  
For this purpose a sequence is duplicative
of its reverse, i.e. [1,2,3,4] == [4,3,2,1], etc.

So am a looking for a function to return all
permutations, excluding duplicates as defined above.

Ideas appreciated.

Art



Thu, 13 May 2004 08:22:05 GMT  
 A permutation on permutations

Quote:

> Was able to find nice stuff on the python-list archives
> as to list permutations, list reversal, and removing
> duplicates from lists.

> My problem is to combine them.

> I am feeding control points to a curve function, and
> want all permutations that result in unique curves.
> For this purpose a sequence is duplicative
> of its reverse, i.e. [1,2,3,4] == [4,3,2,1], etc.

Would [1,3,2,4] be a duplicate?


Thu, 13 May 2004 10:13:16 GMT  
 A permutation on permutations

Quote:
>> I am feeding control points to a curve function, and
>> want all permutations that result in unique curves.
> >For this purpose a sequence is duplicative
> >of its reverse, i.e. [1,2,3,4] == [4,3,2,1], etc.

Tyler asks:

Quote:
>Would [1,3,2,4] be a duplicate?

Nope.

BTW, I just gave an example of a list of length 4.  The  class
itself can accept a list of arbitrary length as an argument.

True enough, I am not fully confident that I have a full handle
on what will create duplicate curves in all cases.  

But I believe I am correct that for the function as
written only list == list.reverse() will create duplicate curves.

Art  



Thu, 13 May 2004 13:54:38 GMT  
 A permutation on permutations
What I've come up with is:

L is my list of arbitrary length.
M= [i for i in range (len(L))]

#thanks to Rainer Deyke's post
def perms(L):
   if list == [] :
      return [[]]
   return [[list[i] + p for i in range(len(list))\
     for p in perms(list[:i] + list[i+1:])]

def removedups(t):
   for p in t:
      m=copy.copy(p)
      m.reverse()
      if m in t:
         t.remove(m)

def drawcurve(t):
   #t is  M or a slice of M
   perm=perms(t)
   removedups(perm)
   for i in range(len(perm)):
      cp=[L[j] for j in perm[i]]
      BezierCurve(cp)

It seems to work.

But I wonder if there is a significantly more
efficient solution

Art



Thu, 13 May 2004 14:18:28 GMT  
 A permutation on permutations
well, i'd like to see this list comprehension
implemented properly ; it doesn't
compute as it stands (on 2.1.1)...?

But i understand the problem;
one way to solve it efficiently is
to choose one permutation out of the
reflected pair, as u build. Unfortunately,
this nice peice of list comprehensions
will (AFAICS) be disposed of.
To choose, eg. pick only perms
whos first entry is less than the last
:)

Simon B

Quote:

>What I've come up with is:

>L is my list of arbitrary length.
>M= [i for i in range (len(L))]

>#thanks to Rainer Deyke's post
>def perms(L):
>   if list == [] :
>      return [[]]
>   return [[list[i] + p for i in range(len(list))\
>     for p in perms(list[:i] + list[i+1:])]

>def removedups(t):
>   for p in t:
>      m=copy.copy(p)
>      m.reverse()
>      if m in t:
>         t.remove(m)

>def drawcurve(t):
>   #t is  M or a slice of M
>   perm=perms(t)
>   removedups(perm)
>   for i in range(len(perm)):
>      cp=[L[j] for j in perm[i]]
>      BezierCurve(cp)

>It seems to work.

>But I wonder if there is a significantly more
>efficient solution

>Art



Thu, 13 May 2004 20:48:53 GMT  
 A permutation on permutations

Quote:

>Was able to find nice stuff on the python-list archives
>as to list permutations, list reversal, and removing
>duplicates from lists.

>My problem is to combine them.

>I am feeding control points to a curve function, and
>want all permutations that result in unique curves.  
>For this purpose a sequence is duplicative
>of its reverse, i.e. [1,2,3,4] == [4,3,2,1], etc.

Can you have the same number appearing twice, e.g. [1,2,3,3] ?

Quote:
>So am a looking for a function to return all
>permutations, excluding duplicates as defined above.

Consider the following source:

def perm(source, done=0, current=[]):
   if done == len(source):
      if current[0] < current[-1]: #removes reversals
         print current
   else:
      for i in source:
         if i not in current:
            perm(source, done+1, current+[i])

d = [1,2,3,4]
perm(d)

When run produces:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 4, 1, 3]
[3, 1, 2, 4]
[3, 2, 1, 4]

--



Thu, 13 May 2004 10:58:17 GMT  
 A permutation on permutations
Simon writes -

Quote:
>well, i'd like to see this list comprehension
>implemented properly ; it doesn't
>compute as it stands (on 2.1.1)...?

Lots of typos in my previous perms function. This
does work - as per Rainer Deyke's post.

def perms(L):
   if L == [] :
      return [[]]
   return [[L[i]] + p for i in range(len(L)) \
     for p in perms(L[:i] + L[i+1:])]

Quote:
>To choose, eg. pick only perms
>whos first entry is less than the last

Good sugestion.

But now it gets real strange - at least
to me.

The following little func does not work as I
would expect!!!

Something about the iteration of p in t
with the list.remove().

Is the func as written certifiably bad
python ,  or a bug/trap I fell into?

M=[1,2,3,4]

def removedups(t):
   for p in t:
      if p[-1]>p[0]:
         t.remove(p)
   print t  

removedups(perms(M))

Note that p in t does not iterate over all
items of the original list, so sublists where
p[-1] > p[0] survive!!!

Art



Fri, 14 May 2004 01:06:28 GMT  
 A permutation on permutations
Phil writes -

Quote:
>Can you have the same number appearing twice, e.g. [1,2,3,3] ?

Actually I hadn't considered double points for what I'm doing.
But I believe that the universe of unique curves would
include curves with double point args. I'll play with it and see
if I can get a better criteria for unique curves.

Quote:
>>So am a looking for a function to return all
>>permutations, excluding duplicates as defined above.
>Consider the following source:
>def perm(source, done=0, current=[]):
>   if done == len(source):
>      if current[0] < current[-1]: #removes reversals
>         print current
>   else:
>      for i in source:
>         if i not in current:
>            perm(source, done+1, current+[i])

Works nice, but I haven't found a great way to get a return
value.  Using a global L=[] in the calling code and
an L.append(current) at "print current" in the perm func.

Thanks.

Art



Fri, 14 May 2004 04:09:38 GMT  
 A permutation on permutations

Quote:

>What I've come up with is:

>L is my list of arbitrary length.
>M= [i for i in range (len(L))]

>#thanks to Rainer Deyke's post
>def perms(L):
>   if list == [] :
>      return [[]]
>   return [[list[i] + p for i in range(len(list))\
>     for p in perms(list[:i] + list[i+1:])]

>def removedups(t):
>   for p in t:
>      m=copy.copy(p)
>      m.reverse()
>      if m in t:
>         t.remove(m)

>def drawcurve(t):
>   #t is  M or a slice of M
>   perm=perms(t)
>   removedups(perm)
>   for i in range(len(perm)):
>      cp=[L[j] for j in perm[i]]
>      BezierCurve(cp)

>It seems to work.

>But I wonder if there is a significantly more
>efficient solution

Assuming that the list of of numbers, and every element in the
list is different, a quick way to test for reversals is to disallow
all lists where the first element is greater than the last one;
this means that you get exactly one of each pair.

--



Fri, 14 May 2004 06:37:02 GMT  
 A permutation on permutations

Quote:

> The following little func does not work as I
> would expect!!!

> Something about the iteration of p in t
> with the list.remove().

> Is the func as written certifiably bad
> Python ,  or a bug/trap I fell into?

> def removedups(t):
>    for p in t:
>       if p[-1]>p[0]:
>          t.remove(p)
>    print t  

It's certifiably bad Python, because modifying a list you're iterating
over is a bug/trap you fell into.  One general way of solving this is
to say for p in t[:]: instead of for p in t[:], but I'd probably say
print [p for p in t if p[-1] > p[0]] instead of the whole function.


Fri, 14 May 2004 10:37:05 GMT  
 A permutation on permutations

Quote:

>Phil writes -

>>Can you have the same number appearing twice, e.g. [1,2,3,3] ?

>Actually I hadn't considered double points for what I'm doing.
>But I believe that the universe of unique curves would
>include curves with double point args. I'll play with it and see
>if I can get a better criteria for unique curves.

>>>So am a looking for a function to return all
>>>permutations, excluding duplicates as defined above.

>>Consider the following source:

>>def perm(source, done=0, current=[]):
>>   if done == len(source):
>>      if current[0] < current[-1]: #removes reversals
>>         print current
>>   else:
>>      for i in source:
>>         if i not in current:
>>            perm(source, done+1, current+[i])

>Works nice, but I haven't found a great way to get a return
>value.  Using a global L=[] in the calling code and
>an L.append(current) at "print current" in the perm func.

That should do the job; or you could pass the list of all permutations
as a second parameter.

BTW, if you change the 1st if statment to

   if len(current) == len(source):

you can get rid of the (done) variable.

--



Fri, 14 May 2004 08:06:34 GMT  
 A permutation on permutations
Sorry for naivet but wouldn't this be a candidate for a filter?
I'm just learning python and diveintopython.org has a section on filters
that looks as if this question was made for it.
http://diveintopython.org/regression_filter.html

-Jeff

Quote:
----- Original Message -----

Newsgroups: comp.lang.python

Sent: Sunday, November 25, 2001 8:37 PM
Subject: Re: A permutation on permutations


> > The following little func does not work as I
> > would expect!!!

> > Something about the iteration of p in t
> > with the list.remove().

> > Is the func as written certifiably bad
> > Python ,  or a bug/trap I fell into?

> > def removedups(t):
> >    for p in t:
> >       if p[-1]>p[0]:
> >          t.remove(p)
> >    print t

> It's certifiably bad Python, because modifying a list you're iterating
> over is a bug/trap you fell into.  One general way of solving this is
> to say for p in t[:]: instead of for p in t[:], but I'd probably say
> print [p for p in t if p[-1] > p[0]] instead of the whole function.

> --
> http://mail.python.org/mailman/listinfo/python-list



Fri, 14 May 2004 11:33:48 GMT  
 A permutation on permutations

Phil writes -

Quote:
>BTW, if you change the 1st if statment to
>   if len(current) == len(source):
>you can get rid of the (done) variable.

But actually the 'done' variable is useful.  By setting
'done' to 2 as an argument -  if 'source'
 is 6 elements, I get back a list of the 4 element
permutations of the 6 elements - excluding reversals as
dups, of course.

Happens to be useful functionality for what I'm
playing with.

Thanks again.

Art



Sat, 15 May 2004 01:52:30 GMT  
 A permutation on permutations

Quote:

> Sorry for naivet but wouldn't this be a candidate for a filter?

Sure.

Quote:
> I'm just learning python and diveintopython.org has a section on filters
> that looks as if this question was made for it.
> http://diveintopython.org/regression_filter.html

Yep.  You'll see the list comprehension construct at the end of that
article is what I suggested.

Quote:

> > to say for p in t[:]: instead of for p in t[:], but I'd probably say

I meant 'instead of for p in t:' --- sorry.


Sat, 15 May 2004 03:02:11 GMT  
 
 [ 14 post ] 

 Relevant Pages 

1. all-permutations is faster than permutation

2. Generating permutations

3. Finding permutations

4. All Permutations

5. All permutations

6. Permutation

7. Permutations

8. Linked list to Permutation vector

9. Permutations

10. Puzzler: function of permutation vector

11. Fwd: re: Puzzler: Permutations and Anagrams

12. Puzzler: Permutations and Anagrams

 

 
Powered by phpBB® Forum Software