#### Archived

This topic is now archived and is closed to further replies.

# algorithm for finding all permutations

This topic is 5309 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Suppose you have a programming problem where you need to ''try every possibility''. This is often reduced to trying all permutations of something. Permutations is a simple concept, but I cant think of an algorithm for it. For example, suppose you have these numbers in an array: 1 2 3 4 What would be an alg to produce all permutations? For eg: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

##### Share on other sites
#include <algorithm>int array[4] = {1, 2, 3, 4};cout << array[0] << ' ' << array[1] << ' ' << array[2] << ' ' << array[3] << endl;for(int i = 0; i < 24; i++){	std::next_permutation(array, array + 4);	cout << array[0] << ' ' << array[1] << ' ' << array[2] << ' ' << array[3] << endl;}

[edited by - aprosenf on May 7, 2004 11:20:31 PM]

##### Share on other sites
Well the C++ answer is to just use std:next_permutation().

However, to actually answer your question, the easiest method to grasp this conceptually is, IMO, recursion. Let''s say you have a set that you want to find all the permutations for. Take all the elements of the set one at a time, and consider the permutations of the remaining elements. In pseudo-code it might look like:
set FindPermutations(set input)  if |input| = 1    return input  else     set return_values = {}    foreach element e in input      subset = input - e      subset_permutations = FindPermutations(subset)      foreach element p in subset_permutations        return_values += p.prepend(e)    return return_values

1. 1
Rutin
43
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633398
• Total Posts
3011661
• ### Who's Online (See full list)

There are no registered users currently online

×