find all possible permutation using backtracking algorithm

[Dani90]

Hi..How do I write backtracking algorithm to find all possible permutation of different integer?

[Manga]

https://www.mathplanet.com/education/algebra-2/discrete-mathematics-and-probability/permutations-and-combinations

[dhayden]

I'm not sure that backtracking is the right algorithm, but you can do it recursively pretty easily. Actually, there's an algorithm for this in the standard library: http://www.cplusplus.com/reference/algorithm/next_permutation/

Assuming that you have to write this yourself, consider the number 1234. The permutations are the union of:
1, followed by all permutations of 234, and
2, followed by all permutations of 134, and
3, followed by all permutations of 124, and
4, followed by all permutations of 123

You can find the permutations of of the 3-digit groups recursively.

Here are some pointers for turning this into code:
- your main "permute" function should take the number, extract the digits into a vector and call the next function to permute the vector.
- the permute function might be

// Permute the digits vector, starting at position whichDigit and
// working down to the last digit.  Print the permutations as integers to output.
void permute_nums(vector<unsigned> &digits, unsigned whichDigit, ostream &output);

The base case is when whichDigit == digits.size().
For the recursive case, swap digits[whichDigit] with digits[whichDigit+1] and recurse,
then swap those digits back and swap digits[whichDigit] with digits[whichDigit+1] and recurse, etc.

- when you print out the result, don't forget about possible leading zeros. It's probably easiest to just reconstruct the permuted number and print it.

[Manga]

Are you wanting to print out all possible permutations?

That quickly turns into a freakin' ton of combinations.

This program calculates just how many...

#include <iostream>

using namespace std;

int factorial(int val) {
	int temp = val;
	for (int i = val-1; i > 0; i--) {
		temp *= i;
	}
	if (temp > 0) {
		return temp;
	}
	else { 
		return 1;
	}
}

int main() {

	int a;
	unsigned int r;

	do {
		cout << "Enter the number of digits between 1 and 10: ";
		cin >> r;
	} while (r < 1 || r > 10);

	a = (factorial(10) / factorial(10 - r));
	cout << a;


	return 0;
}