Collections2 : retrieve size k permutations in a list of n elements

[GoogleCodeExporter]

Collections2.permutations() and Collections2.orderedPermutations() currently 
return all size n permutations within a size n list.

I think adding a way to retrieve size k permutations in a list of n elements 
would be a valuable addition.

See also : 
http://stackoverflow.com/questions/11120985/guava-collections-limit-permutation-
size

Original issue reported on code.google.com by speci...@gmail.com on 21 Jun 2012 at 4:32

[GoogleCodeExporter]

You didn't mention in your SO question any real-world use case.  What are you 
really trying to do?

Original comment by wasserman.louis on 21 Jun 2012 at 5:43

[GoogleCodeExporter]

Original comment by wasserman.louis on 22 Jun 2012 at 12:35

• Added labels: Package-Collect, Type-Addition

[GoogleCodeExporter]

Still waiting on a specific use-case from the OP.

Original comment by kurt.kluever on 24 Jul 2012 at 5:02

• Changed state: Research

[GoogleCodeExporter]

Consider whatever engine generates crosswords for the California lottery.  It 
is given a list of lists where each inner list contains 22 words that have been 
chosen for printing and its task is to supply each ticket with a set of "Your 
Letters" such that the published prize distribution is accurately maintained.

To do that, it has to select a certain number of tickets at each prize level 
and find a k-permutation of the alphabet such that the exacy number of words 
from the set of 22 are completely covered, no more, no less.  Word lists can be 
presumed to have a healthy distribution of letters across words, and if a given 
ticket somehow lacks a solution for the desired prize level, it's always 
possible to swap it for another candidate that does.

Since each ticket gives its player 18 out of 26 letters, it would be useful to 
have a way to iterate through the 18-permutations of A-Z.  Mind you, this 
problem is better addressed by tracking the pair substitutions along a 
Hamiltonian cycle through all the nodes representing unique 18-permutations.  
There is an algorithm for generating such a pair sequence to be found in Knuth 
and I've frequently used the attached implementaiton of it in my own work...

Original comment by jhein...@gmail.com on 14 Aug 2014 at 2:09

Attachments:

• Twiddler.scala

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:14

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08

• Added labels: Restrict-AddIssueComment-Commit