[SciPy-User] all unique permutations

[josef.pktd at gmail.com]

On Thu, Apr 28, 2011 at 10:18 PM, Bruce Southey <bsouthey at gmail.com> wrote:
> On Thu, Apr 28, 2011 at 8:49 PM,  <josef.pktd at gmail.com> wrote:
>> On Thu, Apr 28, 2011 at 9:25 PM, Alan G Isaac <alan.isaac at gmail.com> wrote:
>>> On 4/28/2011 9:12 PM, josef.pktd at gmail.com wrote:
>>>> I didn't find any iterator that would give unique values
>>>
>>> It's true that itertools.permutations is  based on index
>>> permutations, but when the number of permuations is not
>>> huge, it is pretty cheap to form a set or a Counter.
>>
>> But it won't be an iterator anymore, and we need the entire set at once.
>>
>> I would like to go for big, maybe not huge, (and I'm still missing
>> several other pieces and I still don't have an efficient code.)  The
>> target are exact permutation tests where the number of permutations
>> grows very fast, (some papers by Mielke that I don't find right now.)
>>
>>>>> len(list(itertools.permutations([0,0,0,0,0,1,1,1,1])))
>> 362880
>>>>> len(list(permit([0,0,0,0,0,1,1,1,1])))
>> 126
>>>>>
>>>>> len(list(permit([0,0,0,0,0,1,1,1,1,1,1])))
>> 462
>>>>> len(list(itertools.permutations([0,0,0,0,0,1,1,1,1,1,1])))
>> Traceback (most recent call last):
>>  File "<stdin>", line 1, in <module>
>> MemoryError
>>>>>
>>
>> it stopped at around 1.5 gigabyte according to taskmanager
>>
>> Josef
>>
>>
>>>
>>> fwiw,
>>> Alan
>>>
>>> _______________________________________________
>
>> is there a copyright on basic algorithms ?
> IANAL but yes because translation from one [computer] language to
> another is still a derivative work. Rather the real question should be
> if there is in fact a valid copyright in the first place. In these
> cases probably not because many of these are probably already in
> public domain.
>
>
> I have not looked for ages, but I did find some recipes at
> activestate. A simple search gives many recipes such as:
> http://code.activestate.com/recipes/66463-permutation/
>
> Actually the comments are often more helpful...

I forgot to look there

most algorithms go by positions but I found two that drop duplicates

http://code.activestate.com/recipes/496819/
http://code.activestate.com/recipes/496869-computing-permutations-with-duplicates/

They are cleaner than mine, and I didn't know or remember that
recursive function can "yield"
The stop criterion in the unittests in the second recipe is even worse
than mine, but should work well if I figure out how to calculate the
number of unique permutations.

Thanks

Josef

>
> Bruce
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>