Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 0 down vote favorite

The challenge: Generate a list of all possible input combinations given a finite list of inputs and the length of the combinations. The twist is that the combinations should be ordered so that each subsequent combination builds on the last one. Faster is better.

ex:

Given A, B and C, the dumb list would be AAA, AAB, AAC, ABA, ABB, etc.

Optimally ordered, you would get: AAA, AAB, ABA, BAA, AAC, ACA, CAA, *, ABC, BCA, CAB, etc.

So the user can simply input AABAACAA to test 7 combinations, then start over from ABC. Interruptions in the sequence are allowed.

The challenge comes from the newly released game Fez and would be used to attempt to brute force a solution to a problem (by splitting chunks of inputs between multiple users).

I wrote an implementation of what I want (with additional constraints like a character can never repeat three times in a row) in this gist but I really don't think this is optimal.

share|improve this question
2  
@Peter make that an answer and I'll accept it. – mbillard Apr 17 '12 at 23:08
Nah, that would be off-topic. The Wikipedia article suggests that there are a number of different algorithms for generating them, so this could be a good code golf question. If you want me to rewrite it as such for you, just say so. – Peter Taylor Apr 18 '12 at 8:07
Well I wrote the exact algorithm using Ruby and it is quite efficient and would satisfy my requirements. Anyway, thanks because it really helped me. – mbillard Apr 18 '12 at 12:10

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.