# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 December 22 2011

geek
Member

### [Exercise] Permutations/Combinations

Generate all the permutations of a list using a recursive formulation.
Generate all the (subsets of a set)/(combinations of a list) using a recursive formulation.

## #2 December 22 2011

Member

### Re: [Exercise] Permutations/Combinations

Harder!

``````import java.util.ArrayList;

/**
*
*/
public class PermsAndCombs {

private static ArrayList<String> perms, combs;

static {
combs = new ArrayList<String>();
perms = new ArrayList<String>();
}

public static void main(String[] args) {
//generate and display perms:
displayPerms();
//generate and display combs:
displayCombs();

}

public static void generatePerms(String s) {
perms.clear();
noRepetitionPerm(s);
}

public static void generateCombs(String s) {
combs.clear();
noRepetitionComb(s);
}

private static void display(ArrayList<String> l) {
for (String s : l) {
System.out.println(s);
}
}

public static void displayPerms() {
System.out.println();
System.out.println("Permutations : length = " + perms.size());
System.out.println("-----------------");
display(perms);
}

public static void displayCombs() {
System.out.println();
System.out.println("Combinations : length = " + combs.size());
System.out.println("-----------------");
display(combs);
}
//----------------------------- Permutations -------------------------------/

//Helper
public static void noRepetitionPerm(String s) {
noRepetitionPerm(s, "");
}

private static void noRepetitionPerm(String s, String sub) {
int l = s.length();
if (l == 0) {
return;
}

for (int i = 0; i < l; ++i) {
noRepetitionPerm(s.substring(0, i) + s.substring(i + 1, l), sub + s.charAt(i));
}

}
//----------------------------- Combinations -------------------------------/

//Helper
public static void noRepetitionComb(String s) {
noRepetitionComb(s, "");
}

private static void noRepetitionComb(String s, String sub) {

for (int i = 0; i < s.length(); ++i) {
noRepetitionComb(s.substring(i + 1), sub + s.charAt(i));
}
}
}``````

Output :

``````run:

Permutations : length = 120
-----------------
Naedr
Naerd
Narde
Nared
Ndaer
Ndare
Ndear
Ndera
Ndrae
Ndrea
Neard
Nedar
Nedra
Nerda
Nraed
Nrdae
Nrdea
Nreda
aNder
aNdre
aNedr
aNerd
aNrde
aNred
aeNdr
aeNrd
aedNr
aedrN
aerNd
aerdN
arNde
arNed
ardNe
ardeN
areNd
aredN
dNaer
dNare
dNear
dNera
dNrae
dNrea
daNer
daNre
daeNr
daerN
darNe
dareN
deNar
deNra
deaNr
dearN
derNa
deraN
drNae
drNea
draNe
draeN
dreNa
dreaN
eNard
eNdar
eNdra
eNrda
eaNdr
eaNrd
earNd
eardN
edNar
edNra
edaNr
edarN
edrNa
edraN
erNda
eraNd
erdNa
erdaN
rNaed
rNdae
rNdea
rNeda
raNde
raNed
raeNd
raedN
rdNae
rdNea
rdaNe
rdaeN
rdeNa
rdeaN
reNda
reaNd
redNa
redaN

Combinations : length = 32
-----------------

N
Na
Nae
Naer
Nar
Nd
Nde
Nder
Ndr
Ne
Ner
Nr
a
ae
aer
ar
d
de
der
dr
e
er
r
BUILD SUCCESSFUL (total time: 0 seconds)``````

Last edited by Nader.Sleiman (December 22 2011)

## #3 December 22 2011

geek
Member

### Re: [Exercise] Permutations/Combinations

nice and neat. harder? use tail recursion.

## #4 December 22 2011

Joe
Member

### Re: [Exercise] Permutations/Combinations

Harder than expected, I only did the combinations so far.
In Python:

``````def recursive_comb(arg):
if len(arg) <= 1:
yield arg
arg = []

for i in arg:
cpy = list(arg[:])
cpy.remove(i)

for elt in recursive_comb(cpy):
yield [i] + elt``````

Output

>>> reccomb(range(3))
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

Lunch break is almost over, will work on the second part tonight if I have some time.

Last edited by Joe (December 22 2011)

## #5 December 22 2011

Joe
Member

### Re: [Exercise] Permutations/Combinations

[troll]On the other hand, Java is a verbose nightmare of blah.. ><
I do not miss this language[/troll]

## #6 December 22 2011

Member

### Re: [Exercise] Permutations/Combinations

rahmu wrote:

[troll]On the other hand, Java is a verbose nightmare of blah.. ><
I do not miss this language[/troll]

Aw Thanks .. ^.^

Well,Python and c++ are excellent <3, i just use Java since its cool (Cross-Platformal and no pointers)  and is powerful nowadays ,and i do understand that sometimes it might sucks for native stuff and further optimization , for that i do code c++ whenever its best to be used @ , however , i barely know some Python syntax , would maybe like to learn  the whole language elements since Python is quite powerful as well :)

## #7 December 22 2011

arithma
Member

### Re: [Exercise] Permutations/Combinations

@rahmu: Can you please double check your code. Seems like there's no recursion or there's a bad reference there "myfunc" maybe.

## #8 December 22 2011

Joe
Member

### Re: [Exercise] Permutations/Combinations

Corrected. Good eye arithma, it was indeed "myfunc" I did not want to publish a silly func name like this. I also may have confused combinations with permutations. But you get the gist of it. A couple hours I'll be home and do the rest of the exercise.

## #9 December 25 2011

arithma
Member

### Re: [Exercise] Permutations/Combinations

@Nader: If there is any repetition in the input, there will be repetition in your output. You should have stuck with a count for the input or catered for the case of repetition.

## #10 December 26 2011

Member

### Re: [Exercise] Permutations/Combinations

arithma wrote:

@Nader: If there is any repetition in the input, there will be repetition in your output. You should have stuck with a count for the input or catered for the case of repetition.

sure but considering i wrote this to be viewed by coders and meant to show the recursive algos , it wasn't really necessary to add fail-safes :).

## #11 December 26 2011

arithma
Member

### Re: [Exercise] Permutations/Combinations

If I were you I would have considered it an additional challenge.