₦airaland Forum

Hey guys, am going to be dropping some nice coding challenges. You are free to and not to participate.

Challenge A
Your task is to write code that generates the permutations of a word.

So when given the word 'eat' as input, your program should return a list containing

eat
eta
aet
ate
tea
tae

as output.

Time Limit: 1s
Goodluck,

*************NO TIME,,,,,,,,,,,LEMME JUST SKETCH (ROUGH WORK)****************


Lets say we wanna generate permutation for the word SLEEVE

this aint really hard to do> i would have given the code straight up, but cos of my busy schedule, i'ma just explain what i intend to do, maybe somebody can help spit the code.

Permutation means the number of ways letters can be arranged to form a word (whether they make sense or not)
. In this case, we have 6 letters in SLEEVE.

that 6 * 5 * 4 * 3 * 2 * 1, thats 6! (six factorial), i will loop this (downward counting loop). and the iteration of each value must be multiplied against the value.

1st loop = 6
2nd loop = 6 * 5 = 30
3rd loop = 4 * 30 = 120
4th loop = 3 * 120 = 360 . . . complete the remaining loops yourslves

Then its easy to make a factorial function that handles the factorials. this really depnds on whether we are putting order into consideration or not,

Formula

n_P_k = n! / (n - k)!

Thus SLEEVE & permutation 2 will yield,

6_P_2 = 6! / (6 - 2)!
= 6! / 4!
= 6 x 5 = 30 perms.

easily done,,,,create a 2-parameter function

1= number of objects
2= permutations

plugging this into the equation along with a couple of calls to the new factorial functions will return the interger value

kapish!!!!!!!!!!!!!!! c'est finis!!

************AND HERE COMES THE CODE***************** JAVA*************


public class Permutation{

public static void main(String []args)

{

permute("key";

}

private static void permute(String str)

{

int length = str.length();

boolean used[] = new boolean[length];

StringBuffer out = new StringBuffer();

char[] in = str.toCharArray();

doPermute(in, out, used, length, 0);

}

private static void doPermute(char[] in, StringBuffer out, boolean []used, int length, int level)

{

if(level == length)

{

System.out.println(out.toString());

return;

}

for(int i = 0; i < length; i++)
{

if(used[i])

continue;

out.append(in[i]);

used[i] = true;

doPermute(in, out, used, length, level+1);

used[i] = false;

out.setLength(out.length()-1);

}

}

}



kapish!!!!!!!!!!!!!!! c'est finis!!

No standard libraries

Here my code by the way:

import java.util.*;
class PermutationGenerator
{
	private String word;
	
	public static void main(String[] args)
	{
		PermutationGenerator generator = new PermutationGenerator("eat";
		ArrayList<String> permutations = generator.getPermutations();
		for(String s: permutations)
		{
			System.out.println(s);
		}
	}
	
	public PermutationGenerator(String word)
	{
		this.word = word;
	}
	
	public ArrayList<String> getPermutations()
	{
		ArrayList<String> permutations = new ArrayList<String>();
		
		//base case for empty string
		if(word.length() <= 1)
		{
			permutations.add(word);
			return permutations;
		}
		
		for (int i=0; i<word.length(); i++)
		{
			//form simpler word by removing ith character
			String shorterWord = word.substring(0,i) + word.substring(i+1);
			//generate all permutations from the shorterword
			PermutationGenerator shorterPermutationGenerator = new PermutationGenerator(shorterWord);
			ArrayList<String> shorterWordPermutations = shorterPermutationGenerator.getPermutations();
			
			//add the removed character to the front of each permutation of the simpler word
			for(String s: shorterWordPermutations)
			{
				permutations.add(word.charAt(i)+s);
			}
		}
		return permutations;
	}
}

It programmed the OO way for reuse,

I only understand halft of that code tho. Does it work? I mean dd you try the sample input?

HAhaha naa was just asking if you tried it. Its too easy for u so might not even bother testing. Do the compilers come installed with linux? Cause i kinda like have ll compilers here waitin, Mac is just the best .lol How about calculating the program run time, ?

All my permutations are in a list Just take out the for-loop in the main method and the ArrayList permutations is your list,

public static void main(String[] args)
	{
		PermutationGenerator generator = new PermutationGenerator("eat";
		ArrayList<String> permutations = generator.getPermutations();


	}

Y arent u online(YM)

Hmm doesn't linux have ym? or what chat app do u use on linux

lol, thats like the main stuff i do apart from developing,