[wplug] OT - programming logic help

[Ryan W. Frenz]

> On Thu, Apr 23, 2009 at 10:58 AM, Chris Romano <romano.chris at gmail.com> wrote:
>> Here are all the possible combos ... (it's easy to do on paper, just
>> can't figure how to do this with code).

Hi Chris,

The below is in C++, but like you said, the logic should transfer to
any language.  The key is the recursion.

Ryan

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> NumberList;
typedef std::vector<NumberList> ListPermutation;

ListPermutation getPermutations(NumberList numbers) {
	ListPermutation returns;

	// Prune the recursion, just return both permutations of the pair.
	if (numbers.size() == 2) {
		returns.push_back(numbers);
		std::swap(numbers[0], numbers[1]);
		returns.push_back(numbers);
		return returns;
	}

	int index = 0;
	for (NumberList::const_iterator nIt = numbers.begin(); nIt !=
numbers.end(); ++nIt, ++index) {
		// Remove the current number and compute permutations of the others.
		NumberList otherNumbers(numbers);
		otherNumbers.erase(otherNumbers.begin() + index);

		// Add the 'fixed' number to the sub-permutations.
		const ListPermutation subPerm = getPermutations(otherNumbers);
		for (ListPermutation::const_iterator lpIt = subPerm.begin(); lpIt !=
subPerm.end(); ++lpIt) {
			NumberList fullPerm;	fullPerm.push_back(*nIt);
			fullPerm.insert(fullPerm.end(), (*lpIt).begin(), (*lpIt).end());
			returns.push_back(fullPerm);
		}
	}

	return returns;
}

int main(int argc, char* argv[]) {
	NumberList vals;
	vals.push_back(1);
	vals.push_back(2);
	vals.push_back(3);
	vals.push_back(4);
	vals.push_back(5);

	const ListPermutation perms = getPermutations(vals);
	for (ListPermutation::const_iterator pIt = perms.begin(); pIt !=
perms.end(); ++pIt) {
		for (NumberList::const_iterator ppIt = (*pIt).begin(); ppIt !=
(*pIt).end(); ++ppIt)
			std::cerr << *ppIt << " ";
		std::cerr << "\n";
	}
}


-- 
Ryan W. Frenz
rfrenz at gmail.com