CareerCup

void PrintPermutations( std::vector< std::pair<int,bool> > & input 
					   , std::vector<int> & current 
					   , int currentI 
					   , int maxN )
{
	if ( maxN > currentI)
	{
		for ( int i = 0 ; i < maxN; ++i )
		{
			if ( input[i].second == false )
			{
				input[i].second = true;
				current[currentI] = input[i].first;

				PrintPermutations( input , 
					current , 
					currentI + 1 , 
					maxN );

				input[i].second = false;
			}
		}

	}
	else
	{
		std::for_each( 
			current.begin() , 
			current.end() , 
			[](int x )
		{
			std::cout << x << ' ';
		});

		std::cout << std::endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	const int N = 4;
	std::vector< std::pair<int,bool> > input;

	for ( int i = 0 ; i < N ; ++i )
	{
		input.push_back( std::make_pair( i + 1 , false ) );
	}

	std::vector<int> current( N );

	PrintPermutations( input , current ,  0 , N);

	return 0;
}

void permutations(vector<int> &vec,int i)
{
if ( i == vec.size() )
{
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout," "));
cout<<endl;
return;
}

for (int j=i; j<vec.size(); j++)
{
swap(vec[i],vec[j]);
permutations(vec, j+1);
swap(vec[i], vec[j]);
}
}

void test1()
{
int arr[] = {1,2,3,4};
vector<int> vec(arr,arr+4);

permutations(vec, 0);
}

private static void Combinations(ArrayList<Integer> indices, int n) 
    {
        if(indices.size() < n)
        {
            for(int i = 0; i < n; i++)
            {
                if(!indices.contains(i))
                {
                    indices.add(i);
                    Combinations(indices, n);
                    indices.remove(indices.size() - 1);
                }
            }
        }
        if(indices.size() == n)
        {
            for(int i = 0; i < n; i++)
                System.out.print(indices.get(i) + 1);
            System.out.println();
        }
    }

Not bothered about complexity ;)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

template <class BidirectionalIterator>

bool permuteRec(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first,jj=first;
++i;
if (i == last) return false;

std::cout<<"\n";
while(jj!=last){std::cout<<*jj; jj++;}

i = last;
--i;

for(;;) {
BidirectionalIterator ii = i--;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*--j));
std::iter_swap(i, j);
std::reverse(ii, last);
permuteRec(first,last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}

int main()
{
int permute[]={1,2,3,4};
permuteRec(permute,permute+4);
}

List list;
int permut(int x,int n)//x is initially 1 and n is the maximum value
{
if(x==n)
print(list);
else
{
for(int i=0;i<x;i++)
{
add x to ith gap between numbers of list;
permut(x+1,n);
}
}
remove x from list;
}

example: lets we have to print permut of 1 to 4;

so we call permut(1,4)
if(x==n)//here its no
so in else list will have 1
again permut(2,4) will be called so
we have again if(x==n) not satisfied so in else we have

the loop will be executed twice for i=0 and i=1
for i=0 we have list 2,1 and call permut(3,4) & for i=1 we have list 1,2 and call permut(3,4)...
like this we will get once 4,3,2,1 then our for loop finishes so control will come out
and then remove will remove 4 to have in list 3,2,1 for loop continues which is left in recursion
and this time 4 will be inserted in 2nd pos to make the list 3,4,2,1
like this it continues

1
/ \
/ \
2,1 1,2
/|\ /|\
/ | \ / | \
/ | \ / | \
3,2,1 2,3,1 2,1,3
/ | | \
4,3,2,1

correct me if I m wrong

a[] = "cab"
1. Sort the array to make it 'abc'
2. Using already permuted substrings that ends at last location, extend the solution by swapping characters in processed string with adjacent previous char

P(i)
	if(i == 0)
		print a[]
		return
	for each k from i to n-1
		swap(i, k)
		P(i-1)
		swap(i,k)

main()		
	QS()
	P(n-1)

Howz this :


//
// main.c
// LexPrint
//
// Created by Srikant Aggarwal on 03/12/11.
// Copyright 2011 NSIT. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

void swap(int A[], int index1, int index2)
{
if(index1 != index2)
{
A[index1] = A[index1] + A[index2];
A[index2] = A[index1] - A[index2];
A[index1] = A[index1] - A[index2];
}
}

void recurse_print(int A[], int n, int length)
{
if(length == 1)
{
for(int i = 0; i < n; i++)
printf(" %d", A[i]);
printf("\n");
}
else
{
for(int i = n - length; i < n; i++)
{
swap(A, n-length, i);

recurse_print(A, n, length-1);

swap(A, n-length, i);
}
}
}

int main (int argc, const char * argv[])
{
int *A;
int n;

scanf("%d", &n);

if(n > 0)
{
A = (int *)malloc(sizeof(int)*n);

for(int i = 1; i <= n; i++)
A[i-1] = i;

recurse_print(A, n, 4);
}

return 0;
}

One more method:

//
//  main.c
//  PrintPermutations
//
//  Created by Srikant Aggarwal on 09/12/11.
//  Copyright 2011 NSIT. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

void swap(int A[], int index1, int index2)
{
    if(index1 != index2)
    {
        A[index1]=A[index1]^A[index2];
        A[index2]=A[index1]^A[index2];
        A[index1]=A[index1]^A[index2];
    }
}

void reverse(int A[], int begin, int end)
{
    int i = 0;
    
    while((begin+i) <= (end+begin)/2)
    {
        swap(A, begin+i, end-i);
        i++;
    }
}

void print_permutations(int A[], int n)
{
    int i = n-2, j=n-1, k=n-1, l;
    unsigned char continue_loop = 1;
    
    for(l=0; l < n; l++)
        printf(" %d ", A[l]);
    
    while(continue_loop)
    {
        i = n-2, j=n-1, k=n-1;
        continue_loop = 0;
        while(i >= 0)
        {
            if(A[i] < A[j])
            {
                while(k > i)
                {
                    if(A[i] < A[k])
                    {
                        swap(A, i, k);
                        reverse(A, j, n-1);
                        printf("\n");
                        for(l=0; l < n; l++)
                            printf(" %d ", A[l]);
                        break;
                    }
                    k--;
                }
                continue_loop = 1;
                break;
            }
            i--;
            j--;
        }
    }

}

int main (int argc, const char * argv[])
{
    int i = 0, n;
    int *A;
    
    scanf("%d", &n);
    A = (int *)malloc(sizeof(int));
    
    for(; i < n; i++)
        A[i] = i+1;
    
    print_permutations(A, n);
}

void permutate( char[] str, int index )
{
    int i = 0;
    if( index == strlen(str) )
    { // We have a permutation so print it
        printf(str);
        return;
    }
    for( i = index; i < strlen(str); i++ )
    {
        swap( str[index], str[i] ); // It doesn't matter how you swap.
        permutate( str, index + 1 );
        swap( str[index], str[i] );
    }
}

taken from online, not by me