Creating unique permutations

[Chris C]

Following a recent discussion in the channel I had a quick play with
creating unique permutations of a list of items. By unique I mean set
unique, so given the input [a,b] the output would be [ [a], [a,b],
[b] ] but would not include [b,a].

I've created a temporary branch just to preview the result:
http://gitorious.org/~chilversc/cadenza/chilversc-cadenza/commit/b75d4d5b419d20572d3534f9a28b12edd0d0bdc9

It currently just uses a simple recursive method to create the list of
items, its also a little wasteful on the input enumerator, using Any,
First and creating a chain of Skip(1), but I thought I'd throw up an
initial version and see what people thought.

[Jonathan Pryor]

Very nifty.

You've already seen my comments on the commits.

I would suggest using just .Combinations() or .Permutations() instead of
the current .UniqueCombinations(). I don't think "Unique" adds that
much to the method name.

I think .Permutations() sounds better.

Thanks!

- Jon

[Chris C]

Having looked at it some more I think the correct name is Subsets,
combinations and permutations actually have specific meanings, namely
combinations are a fixed size and an unordered set, and a permutation
is an ordered combination.

The list based method seems pretty reasonable if you want all subsets,
and the upper limit of 64 items I'd say is acceptable given the huge
number of subsets that would generate. The only thing I don't like is
that it has to wait until its actually enumerating before it throws,
but the alternative would require evaluating the .ToList() in the main
Subset method which would prevent lazy evaluation of .ToList(), I'm
not sure which is worse.

For combinations I was looking at http://compprog.wordpress.com/2007/10/17/generating-combinations-1/
and subsets could be implemented as just a series of combinations with
increasing size until the list's length is reached (this would just
save having two sets of code that does fairly similar stuff).

I've also been looking at how to implement a version that accepts a
function to prune the subsets, i.e. if it returns false to [a,b] it
means anything with the subset [a,b] will be pruned, e.g. [a,b],
[a,b,c], etc. If you have a lot of items and an aggressive prune
method the recursive method seems to be the better choice as removing
a subset immediately prevents all other subsets containing that subset
from being evaluated.

On Dec 19, 3:13 pm, Jonathan Pryor <jonpr...@vt.edu> wrote:
> Very nifty.
>
> You've already seen my comments on the commits.
>
> I would suggest using just .Combinations() or .Permutations() instead of
> the current .UniqueCombinations().  I don't think "Unique" adds that
> much to the method name.
>
> I think .Permutations() sounds better.
>
> Thanks!
>
>  - Jon
>
>
>
> On Fri, 2009-12-18 at 19:17 -0800, Chris C wrote:
> > Following a recent discussion in the channel I had a quick play with
> > creating unique permutations of a list of items. By unique I mean set
> > unique, so given the input [a,b] the output would be [ [a], [a,b],
> > [b] ] but would not include [b,a].
>
> > I've created a temporary branch just to preview the result:

> >http://gitorious.org/~chilversc/cadenza/chilversc-cadenza/commit/b75d...