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.

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

 Page 1 of 1 [ 14 post ]

Relevant Pages