CareerCup

ArrayList<String> permutationsOf(String s)
{
     ArrayList<String> result = new ArrayList<String>();
 if (s.length() == 1)
{ // base case
         // return a new ArrayList containing just s         result.add(s);
         return result;
     }
       else 
       {         // separate the first character from the rest
          char first = s.charAt(0);
           String rest = s.substring(1);
         // get all permutationsOf the rest of the characters          ArrayList<String> simpler = permutationsOf(rest);  // recursive step          // for each permutation,   for (String permutation : simpler) 
   { // extra work
     // add the first character in all possible positions, and             ArrayList additions = insertAtAllPositions(first, permutation);
            // put each result into a new ArrayList             result.addAll(additions);
         }
         return result;
     }
 }
private ArrayList<String> insertAtAllPositions(char ch, String s) 
{
     ArrayList<String> result = new ArrayList<String>();
for (int i = 0; i <= s.length(); i++)
{
         String inserted = s.substring(0, i) + ch + s.substring(i);
         result.add(inserted);
      }
     return result;
}

Isnt this just the simple Factorial question , tweaked slightly ??

This is kind of factorial question. But we need to print all the permutations of input number. Ex: if the input number is 123. Convert the integer to string(use toString method), Then pass the string to permutationsOf("123") method. There are 3! permutations of the number. The result is
123
213
231
132
312
321

Can anyone explain the algorithm to print all possible permutation for the given number
( write the function )

I would do the circular link list

How can one do with circular linked list? I think its impossible!

How can one do with circular linked list? It does not make sense.

// Integer_Permutation.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

void main()
{
	vector<int> iV;
	int num,first,f,second,s,third,fourth;
	cout<<"ENTER PASSWORD : ";
	cin>>num;
	first = num/1000;
	f = num%1000;
	second = f/100;
	s=f%100;
	third = s/10;
	fourth =s%10;
	
	
	iV.push_back(first);
	iV.push_back(second);
	iV.push_back(third);
	iV.push_back(fourth);

	cout << "ENTERED PASSWORD : ";
	copy(iV.begin(),iV.end(),ostream_iterator<int>(cout,""));
	cout <<endl;

	cout <<"ALL COMBINATIONS OF THE PASSWORD: \n\n";
	
	
	while(next_permutation(iV.begin(),iV.end()))
	{
		copy(iV.begin(),iV.end(),ostream_iterator<int>(cout,""));
		cout <<endl;
	}

	system("PAUSE");
}

#include "stdafx.h"
#include<conio.h>
#include<stdlib.h>
#include<time.h>

void swapString(char*, int, int);
void rotateString(char*, int);

int _tmain(int argc, _TCHAR* argv[])
{
char original[5] = {'1', '2', '3', '4', '\0'};
char buff[5] = {'1', '2', '3', '4', '\0'};
int i, j, rem, n=3;

/*printf("Enter a 4-digit password: ");
scanf("%s", buff);*/

printf("The 4-digit password is: %s\n\n", buff);

printf("The combinations are:\n\n[00] %s\n", buff);

for(i=1; i<24; i++)
{
rem = i%2;

if(i>5 && i%6==0)
{
rotateString(original, n);
printf("[%02d] %s\n", i, original);

for(j=0; j<=n; j++)
buff[j] = original[j];
}
else
{
switch (rem)
{
case 1:
swapString(buff, n-1, n);
printf("[%02d] %s\n", i, buff);
break;
case 0:
swapString(buff, n-2, n-1);
printf("[%02d] %s\n", i, buff);
break;
default:
break;
}
}
}

getch();

return 0;
}

void swapString(char *buff, int a, int b)
{
char temp = buff[a];
buff[a] = buff[b];
buff[b] = temp;
}

void rotateString(char *buff, int n)
{
int i;
char temp = buff[0];

//printf("------------------\n");
for(i=0; i<n; i++)
{
buff[i] = buff[i+1];
//printf("%s\n", buff);
}
//printf("------------------\n");
buff[n] = temp;
}

//n is password string converted to int

//In main
int n = int.parse(console.readline());
Console.writeline("Combination of given pwsd is " + pswdCombi(n);

//function
static int pswdCombi(int n)
{
int _c = 1;
for (int i = 1; i <= n.ToString().Length; i++)
{
_c*= i;
}

return _c;
}

I have the permutation code running and I did it using recursive functions..

What if the password has repeated characters?

#include<iostream>
#include<string>

using namespace std;

void permute(string str,int start)
{
     int i;
     
     if(start==str.size()-1)
     cout<<str<<"\n";
     
        for(i=start;i<str.size();i++)
        {
         swap(str[i],str[start]);
         permute(str,start+1);
         swap(str[i],str[start]);
         
         }
         
         }

c'on guys...its pretty simple..use the following simple solution,

#include<iostream>
#include<string>
using namespace std;
void permute(string s, int i = 0) {
    if (i == s.size()) cout << s << endl;
    else for (int j = i; j < s.size(); ++j) swap(s[i], s[j]), permute(s, i + 1), swap(s[i], s[j]);
}

int main() {
    string t = "123";
    permute(t);

    return 0;
}

just 3 lines of code and we're done!

This comment has been deleted.

#include<stdio.h>
#include<stdlib.h>
int a[]={1,2,3,4};
int p[4]={0};
void permute(int i)
{
        int j;
        int t;
        if(i<4){
                for(j=0;j<4;j++){
                        if(a[j]!=-1){
                                p[i]=a[j];
                                t=a[j];
                                a[j]=-1;
                                permute(i+1);
                                a[j]=t;
                        }
                }
        }
        if(i == 4){
                printf("\n");
                for(j=0;j<4;j++){
                        printf("%d",p[j]);
                }

        }
}
void main()
{
        permute(0);
}

#include<iostream>

void permute(char a[],int i,int j)
{
char temp;
int k=0;
if(i==j)
printf("String is %s\n",a);

else
{
for(k=i;k<j;k++)
{

temp=a[j-1];
a[j-1]=a[k];
a[k]=temp;



permute(a,i,j-1);


temp=a[j-1];
a[j-1]=a[k];
a[k]=temp;

}
}

}

int main()
{

char a[30];
printf("Enter value\n");
scanf("%s",a);

permute(a,0,strlen(a));

printf("Original String is %s\n",a);

system("PAUSE");
exit(0);

}





Change type of array to int

<pre lang="" line="1" title="CodeMonkey21254" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int v[] = {3,4,5,6,9};
int n = v.length;
permute(v, 0, n);
}

public void permute (int[] v, int start_index, int n) {
if (start == v.length - 1)
print(v, n);

else {
for (int i = start_index; i<n; i++) {
int tmp = v[i];
v[i] = v[start];
v[start] = tmp;
permute(v, start+1, n);
v[start] = v[i];
v[i] = tmp;
}
}
}

public void print (int[] v, int n) {
if (v != 0) {
for (int i = 0; i < n; i++) {
System.out.println(v[i]);
}
}
}
}

</pre><pre title="CodeMonkey21254" input="yes">
</pre>

class perm {
	public static void password(char[] pass, int i) {
		if (i == pass.length)
			System.out.println(pass);
		else
			for (int j = i; j < pass.length; j++) {
				swap(pass, i, j);
				password(pass, i + 1);
				swap(pass, i, j);
			}
	}

	private static void swap(char[] text, int i, int j) {
		char c = text[i];
		text[i] = text[j];
		text[j] = c;
	}

	public static void main(String[] args) {

		password("1234".toCharArray(), 0);
	}
}

Hey, guys. I tried to take care of repeated numbers too hence I used HashSet().
Please leave comment if there is a better way or improvement.
Thank you

public static void main(String args[]) {
        int[] pw = {1,2,1,3,1};
        Arrays.sort(pw);
        combo(pw);
    }
    static void combo(int[] pw){
        combo(pw, 0, pw.length, new HashSet());
    } 
    static void combo(int[] pw, int num, int count, HashSet set) {
        if (count == 0) {
            if(set.add(num)){
                System.out.println(num);
            }
            return;
        }
        int[] temp;
        for (int i = 0; i < pw.length; i++) {
            temp = delete(pw, i);
            combo(temp, num * 10 + pw[i],count-1,set);
        }
    }

    static int[] delete(int[] pw, int skip) {
        int[] updated = new int[pw.length - 1];
        for (int i = 0, j = 0; i < pw.length; i++) {
            if (i == skip) {
                continue;
            }
            updated[j++] = pw[i];
        }
        return updated;
    }

import java.util.ArrayList;
import java.util.List;


public class Permutations {

	public static void main(String[] args) {
		List<String> perms = getPerms("123");
		for(String a:perms) {
			System.out.println(a);
		}
	}

	static List<String> getPerms(String input) {
		List<String> permutations = new ArrayList<String>();
		if (input == null) {
			return null;
		} else if (input.length() == 0) {
			permutations.add("");
			return permutations;
		} else {
			String remainder = input.substring(1, input.length());
			List<String> words = getPerms(remainder);

			char first = input.charAt(0);
			for (String word : words) {
				for (int k = 0; k <= word.length(); k++) {
					permutations.add(insertCharAt(first, word, k));
				}
			}
			return permutations;
		}
	}

	private static String insertCharAt(char c, String word, int k) {
		String start = word.substring(0, k);
		String end = word.substring(k);
		return start + c + end;
	}
}

Output:
123
213
231
132
312
321

private static void password(int[] a){
		int[] word = new int[a.length];
		for(int i=0; i< a.length; i++){
			word[0] = a[i];
			print(word, 1, a, a.length-1);
		}
	}
	
	private static void print(int[] word, int pos, int[] a, int len){
		if(len == 0){
			for(int k=0; k<word.length; k++){
				System.out.print(word[k]);
			}
			System.out.println();
			return;
		}
		
		boolean[] flag = new boolean[a.length];
		
		for(int i=0; i<flag.length; i++){
			for(int l=0; l<pos; l++){
				if(word[l] == a[i]){
					flag[i] = true;
				}
			}
		}
		for(int j=0; j<a.length; j++){
			if(flag[j] != true){
				word[pos] = a[j];
				print(word,pos+1, a, len-1);
			}
			
		}
	}