Alexander Bogomolny’s algorithm is used to permute first N natural numbers.
Given the value of N, we have to output all the permutations of numbers from 1 to N.
Examples:
Input : 2
Output : 1 2
2 1
Input : 3
Output : 1 2 3
1 3 2
2 1 3
3 1 2
2 3 1
3 2 1
The idea is to maintain an array to store the current permutation. A static integer level variable is used to define these permutations.
- It initializes the value of the current level and permutes the remaining values to higher levels.
- As the assigning action of the values reaches the highest level, it prints the permutation obtained.
- This approach is recursively implemented to obtain all possible permutations.
C++
// C++ program to implement// Alexander Bogomolny UnOrdered// Permutation Algorithm#include <bits/stdc++.h>using namespace std;// A function implementing// Alexander Bogomolny algorithm.void solve(vector<int>& v, int n, string& s, vector<vector<int> >& vv){ // if all the numbers are added // to the vector if (v.size() == n) { // Append the vector // to the answer vv.push_back(v); return; } for (int i = 0; i < n; i++) { // if the number is not taken if (s[i] != '1') { s[i] = '1'; v.push_back(i + 1); // Recursive call to the function solve(v, n, s, vv); // Backtrakking step s[i] = '0'; v.pop_back(); } }}int main(){ int n = 3; vector<int> v; vector<vector<int>> vv; string s; for (int i = 0; i < n; i++) s += '0'; solve(v, n, s, vv); for (int i = 0; i < vv.size(); i++) { for (int j = 0; j < vv[i].size(); j++) { cout << vv[i][j] << " "; } cout << endl; }} |
Java
// Java program to implement // Alexander Bogomolny UnOrdered // Permutation Algorithmimport java.io.*;class GFG{static int level = -1;// A function to print// the permutation.static void print(int perm[], int N){ for (int i = 0; i < N; i++) System.out.print(" " + perm[i]); System.out.println();}// A function implementing // Alexander Bogomolny algorithm.static void AlexanderBogomolyn(int perm[], int N, int k){ // Assign level to // zero at start. level = level + 1; perm[k] = level; if (level == N) print(perm, N); else for (int i = 0; i < N; i++) // Assign values // to the array // if it is zero. if (perm[i] == 0) AlexanderBogomolyn(perm, N, i); // Decrement the level // after all possible // permutation after // that level. level = level - 1; perm[k] = 0;}// Driver Codepublic static void main (String[] args){ int i, N = 3; int perm[] = new int[N]; AlexanderBogomolyn(perm, N, 0);}}// This code is contributed by anuj_67. |
Python3
# Python3 program to implement Alexander # Bogomolny’s UnOrdered Permutation Algorithm # A function to print permutation. def printn(perm, N): for i in range(N): print(" ",perm[i], sep = "", end = "") print() # A function implementing Alexander Bogomolny # algorithm. level = [-1] def AlexanderBogomolyn(perm, N, k): # Assign level to zero at start. level[0] = level[0] + 1 perm[k] = level[0] if (level[0] == N): printn(perm, N) else: for i in range(N): # Assign values to the array # if it is zero. if (perm[i] == 0): AlexanderBogomolyn(perm, N, i) # Decrement the level after all possible # permutation after that level. level[0] = level[0] - 1 perm[k] = 0 return# Driver code N = 3perm = [0]*NAlexanderBogomolyn(perm, N, 0) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to implement // Alexander Bogomolny UnOrdered // Permutation Algorithmusing System;class GFG{static int level = -1;// A function to print// the permutation.static void print(int []perm, int N){ for (int i = 0; i < N; i++) Console.Write(" " + perm[i]); Console.WriteLine();}// A function implementing // Alexander Bogomolny algorithm.static void AlexanderBogomolyn(int []perm, int N, int k){ // Assign level to // zero at start. level = level + 1; perm[k] = level; if (level == N) print(perm, N); else for (int i = 0; i < N; i++) // Assign values // to the array // if it is zero. if (perm[i] == 0) AlexanderBogomolyn(perm, N, i); // Decrement the level // after all possible // permutation after // that level. level = level - 1; perm[k] = 0;}// Driver Codepublic static void Main (){ int N = 3; int []perm = new int[N]; AlexanderBogomolyn(perm, N, 0);}}// This code is contributed // by anuj_67. |
Javascript
<script>// Javascript program to implement // Alexander Bogomolny UnOrdered // Permutation Algorithmlet level = -1; // A function to print// the permutation.function print(perm, N){ for (let i = 0; i < N; i++) document.write(" " + perm[i]); document.write("<br/>");} // A function implementing // Alexander Bogomolny algorithm.function AlexanderBogomolyn(perm, N, k){ // Assign level to // zero at start. level = level + 1; perm[k] = level; if (level == N) print(perm, N); else for (let i = 0; i < N; i++) // Assign values // to the array // if it is zero. if (perm[i] == 0) AlexanderBogomolny(perm, N, i); // Decrement the level // after all possible // permutation after // that level. level = level - 1; perm[k] = 0;}// driver program let i, N = 3; let perm = Array.from({length: N}, (_, i) => 0); AlexanderBogomolny(perm, N, 0); </script> |
Output
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Time Complexity: O(N*N!), where N is the given integer.
Auxiliary Space: O(N*N!), for storing all the permutations of the first N natural numbers.
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
