C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Implement the Alexander Bogomolny's UnOrdered Permutation Algorithm for Elements From 1 to N



Implement the Alexander Bogomolny's UnOrdered Permutation Algorithm for Elements From 1 to N

- The Alexander Bogomolyn's algorithm is to permute first 'N' natural numbers.
- The time complexity of this algorithm is O(n!).

- This algorithm takes N value.
- It initializes the value current level and permutes the remaining values to the higher levels.
- As the assigning action of the values reaches to the highest level, it prints the permutation obtained.
- Exit.

#include<iostream>
#include<iomanip>
 
using namespace std;
 
// A function to print the permutation.
void print(const int *v, const int size)
{
	int i;
	// Print the array if it is non-empty.
	if (v != 0) 
	{
    		for ( i = 0; i < size; i++)
		{
			cout<<setw(4)<<v[i];
		}
		cout<<"\n";
	}
}
 
// A function implementing Alexander Bogomolyn algorithm.
void AlexanderBogomolyn(int *Value, int N, int k)
{
	static int level = -1;
	int i;
	// Assign level to zero at start.
	level = level+1; 
	Value[k] = level;
 
	if (level == N)
		print(Value, N);
	else
		for (i = 0; i < N; i++)
		// Assign values to the array if it is zero.
			if (Value[i] == 0)
				AlexanderBogomolyn(Value, N, i);
 
	// Decrement the level after all possible permutation after that level.	
	level = level-1;
	Value[k] = 0;
}
 
int main()
{
	int i, N, count = 1;
	cout<<"Enter the N value to permute first N natural numbers: ";
	cin>>N;
	int Value[N];
 
	for (i = 0; i < N; i++)
	{
		Value[i] = 0;
		count *= (i+1);
	}
 
	// Print the permutation's count.
	cout<<"\nThe number of permutations possible is: "<<count;
 
	// Print the permutation.
	cout<<"\n\nPermutation using Alexander Bogomolyn's algorithm: \n";
	AlexanderBogomolyn(Value, N, 0);
 
	return 0;
}