CareerCup

Anybody Answering this question
Please make sure your algo or code works for duplicate characters and it really works. :P

import java.util.Arrays;

public class Permutation {

	public static void main(String args[]) {

		char sorted[] = { 'a', 'a', 'l', 'b' };
		Arrays.sort(sorted);
		permute(sorted, 0);
	}

	public static void permute(char[] word, int k) {

		if (word.length == k)
			System.out.println(word);
		else {
			for (int i = k; i < word.length; i++) {

				if (i + 1 < word.length && word[i] == word[i + 1])
					continue;

				swap(word, i, k);

				for (int l = k + 1; l <= i; l++) {
					if (word[l] > word[i]) {
						swap(word, l, i);
					}
				}
				permute(word, k + 1);

				for (int l = i; l >= k + 1; l--) {
					if (word[l] < word[i]) {
						swap(word, l, i);
					}
				}

				swap(word, i, k);

			}
		}

	}

	private static void swap(char[] s, int index, int i) {
		char temp = s[index];
		s[index] = s[i];
		s[i] = temp;

	}

}

Algorithm :
Sort the string in alphabetical order
forever(;;)
{
for(i=last char in string to 2)
for(j= i-1 to 1)
if (str[i] > str[j]) {
swap(str[i],str[j]);
sort(str from j+1 to end);
break both the loops;
}
if(no swapping and sorting in for loops)
return;
else print string;
}//loop again

//This will output the strings in lexicographical order as in dictionary.

Below program expects lexicographically sorted input.

#include <stdio.h>
#include <string.h>
void swap (char* pArray, int i, int j)
{
	char temp = pArray[i];
	pArray[i] = pArray[j];
	pArray[j] = temp;
}
void perm (char* pArray, int size, int index)
{
	int i,j,k;
	if(size==index)
	{
		printf("%s\n", pArray);
	}
	else
	{
		for(i = index; i < size; i++)
		{
			if((pArray[i] == pArray[index])&&(i != index))
			{
				continue;
			}
			swap(pArray,i,index);
			for(j=index+1;j<=i;j++)
			{
				if(pArray[j]>pArray[i])
				{
					swap(pArray,j,i);
				}
			}
			perm(pArray,size,index+1);
			for(j=i;j>=index+1;j--)
			{
				if(pArray[j]<pArray[i])
				{
					swap(pArray,j,i);
				}
			}			
			swap(pArray,i,index);			
		}
	}
}
int main ()
{
	char array[100];
	gets(array);
	printf("Permutations:\n");
	perm(array,strlen(array),0);
}

Seems like the above code still not working, at least tried for input as "1233" and it gives error: "ArrayIndexOutOfBoundsException: 4"

Any way, here is the code for generating all possible variants, but it is with cashing so far :(

private void swap (char [] str, int i, int j)  {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }
    private void getPossibleCombinations(char [] str, int i, int j, int len){
        
        if ((j - i == 1) && j == len - 1 ){
            Display(str, "");
            if (str[i]!= str[j]){
                swap(str,i,j);
                Display(str, "");
                swap(str,i,j);
            }
        }
        else {
            str = str.clone();
            getPossibleCombinations(str, i+1, i+2, len);
            do{
                if (str[i] != str[j]){
                    swap(str, i, j);
                    getPossibleCombinations(str, i+1, i+2, len);
                }
            }
            while(++j < len);
        }
    }

    //how should be invoked
    getPossibleCombinations(str, 0, 1, str.length);

int dup_permute(char *str, size_t length) {
int count = 0;
std::sort(str, str+length);
do {
++count;
cout << str << '\n';
}
while(std::next_permutation(str, str+length));
return count;
}

<?php
function swap(&$str1,&$str2)
{
$temp=$str1;
$str1=$str2;
$str2=$temp;
}

function permStr($str,$i)
{
//printf("%d",i);
global $n;
global $result;
if($i==(count($str)-1)) {
$result[] = implode('', $str);
//echo '<br>';
}
else
{
for($j=$i;$j<count($str);$j++)
{
//printf("i %d,j %d",i,j);
swap($str[$i],$str[$j]);
permStr($str,$i+1);
swap($str[$i],$str[$j]);
}
}
}

$str = array('a','l','l');
$result = array();
permStr($str,0);
$result = array_unique($result);
foreach ($result as $value){
echo $value.'<br>';
}

Standard library has in built function to produce next permutation of a string

#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
using namespace std;

void print_all_permutations(const string& s)
{
    string s1 = s;
    sort(s1.begin(), s1.end()); 
    do {
        cout << s1 << endl;
    } while (next_permutation(s1.begin(), s1.end()));
}

int main()
{
    print_all_permutations("AAB");
}

void swap(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}
void permutate(vector<int>& A, vector<int>::size_type divider) {
	static int c = 0;
	if(divider == A.size()-1) {
		cout << ++c << ". ";
		for(auto i : A) {
			cout << i;
		}		
		cout << endl;
		return;
	}

	//[0, divider) == sofar, [divider A.size()) -> remaining
	map<int,bool> hash;
	for(auto i = divider; i < A.size(); i++) {
		if(!hash[A[i]]) {
			swap(A[i], A[divider]);
			permutate(A, divider + 1);
			swap(A[i], A[divider]);
			hash[A[i]] = true;
		}
	}
}

PHP Code :

$str = "ababac";

$subSets=array();
$allSubSets=array();
getSubSets($str,$subSets,$allSubSets);

print_r($allSubSets);


function getSubSets($str,$subSet=array(),&$allSubSets=array()){
    for($i=0;$i<strlen($str);$i++){
        $localArray=$subSet;
        $char = $str[$i];
        if(in_array($i,$localArray)) continue;
        $localArray[]=$i;
        if(count($localArray) == strlen($str)){
            $resultArray=array();
            foreach($localArray as $index)
               $resultArray[]=$str[$index];
            if(!in_array($resultArray,$allSubSets)) $allSubSets[] = $resultArray;
        }
        else getSubSets($str,$localArray,$allSubSets);
    }
}

}

My solution. Assume input is lowercase English letters only, thus use bool used[26] array to mark the used character at "that index" on each stack layer. You can use a hash map if the input alphabet set is very huge.

#include <iostream>
#include <ostream>
#include <iterator>
#include <vector>

using namespace std;
  
void doPermutation(vector<char> &input, int index) {
    bool used[26] = {false};
    
    if(index == input.size()) {
        copy(input.begin(), input.end(), ostream_iterator<char>(cout, "") );
        cout << endl;
        
    } else {
      int i, j;
      for(i =index; i < input.size(); i++ ) {
        if(used[ input[i]-'a'] == false) {
           swap(input[i], input[index]);
           doPermutation(input, index+1);
           swap(input[i], input[index]);
           used[input[i]-'a'] = true;
       } 
      }
    }
}

  void permutation(vector<char>& input) {
      doPermutation(input, 0);
  }


int main()
{
   cout << "Hello World" << endl; 
   const char* inp = "alla";
   vector<char> input(inp, inp + 4 );
   
   permutation(input);
   
   return 0;
}

input "all"
output:
all
lal
lla

input : "aall"
output:

alla
alal
aall
lala
laal
llaa

short and simple code here : solvekarlo.com/index.php?subj=2&page=28