What are some practical uses of generating all permutations of a list, such as ['a', 'b', 'c'] ?

Question

I was asked by somebody in an interview for web front end job, to write a function that generates all permutations of a string, such as "abc" (or consider it ['a', 'b', 'c']).

so the expected result from the function, when given ['a', 'b', 'c'], is

abc
acb
bac
bca
cab
cba

Actually in my past 20 years of career, I have never needed to do something like that, especially when doing front end work for web programming.

What are some practical use of this problem nowadays, in web programming, front end or back end, I wonder?

As a side note, I kind of feel that expecting a result in 3 minutes might be "either he gets it or he doesn't", especially I was thinking of doing it by a procedural, non-recursive way at first. After the interview, I spent another 10 minutes and thought of how to do it using recursion, but expecting it to be solved within 3 minutes... may not be a good test of how qualified a person is, especially for front end work.

Answer 1

Practical application (see below) is irrelevant. The interviewers are using this problem to weed out developers that don't know how to code. Effectively it's a FizzBuzz problem.

Some applications of permutations:

• Card sorting
• Table seating
• Shuffle Bag

Answer 2

If you have a problem to solve like the travelling salesman problem which is based on a real life problem, then a simple but inefficient solution is to brute-force every possible permutation and see which is optimal. To do this it can be useful to have a function that generates the permutations. Obviously such a solution won't be practical for even quite small values of n.

For ordinary user interface programming, it seems unlikely you'd need to generate permutations. However it can be useful to know how to write recursive functions in general, For example if you have a tree view in your interface and need to perform an operation on every node in a subtree then a recursive function is a good approach.

Answer 3

If you want to return the results to a query in random order, for example to be fair to each of them. It appears that StackOverflow does this among equally rated answers.

Answer 4

A practical application? Testing event driven software where partial ordering of events means you'll have to test the unordered sections with full permutations of the ordering of those events.

Well, that's besides the practical application of asking candidates if they can do it so we can disqualify some candidates on the grounds that we believe you are a bad programmer if you can't answer this question.

Answer 5

One of my clients is a composer of music (André Cormier), and he asked me to write a permutation calculator to help him choose notes for melodic lines and chords:

http://juliusdavies.ca/andre/note_permute.html

Does that count as a practical application?

Answer 6

Some practical applications include:

Routing / networking / parallel computing

Cryptographic algorithms

Answer 7

One practical application within the gambling industry of generating permutations of symbols is to generate configuration tables to prove that no one combination of symbols appears more than any other symbol for win/loss configurations.

For example, take the canonical slot machine with 3 columns of bars, cherries, and keys. You don't want it to be that every single loser configuration is [cherry, bar, key] or the users will get pissed off. You also don't want it so that every time a [cherry, bar, key] combination comes up the next game is 100% guaranteed a winning combination.

It's beyond practical in the gambling industry: There are times when that's all you do in a working day.

Answer 8

Most permutation methods - generate a random permutation, generate a particular numbered permutation, stepping to the sequentially next/previous permutation, or generating all permutations - are very useful for one specific thing that a programmer should be doing a lot of...

Generating input data for unit tests.

Of course you should just have the algorithms in a library - preferably a standard one. Personally, I'd trust someone who takes ten or fifteen minutes to figure out a permutation-stepping algorithm more than someone who regurgitates it instantly - it isn't something you need to write every day (or every year, even) so keeping it memorised is a waste of neurons that could be doing a more useful job.

I might even award pragmatism points to the guy who gets his phone out and Googles it.

Answer 9

Testing a sorting algo.

Answer 10

Questionable but practical use: Finding anagrams, useful for cracking passwords.

Answer 11

We've been doing this for calculating wilds in slot machine reels :)