[Exercise] Permutations/Combinations

geek

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.

nader-sleiman

Harder!

import java.util.ArrayList;

/**
 *
 * @author Nader Sl.
 */
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:
        generatePerms("Nader");
        displayPerms();
        //generate and display combs:
        generateCombs("Nader");
        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) {
            perms.add(sub);
            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) {
        combs.add(sub);

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

Output :

run:

Permutations : length = 120
-----------------
Nader
Nadre
Naedr
Naerd
Narde
Nared
Ndaer
Ndare
Ndear
Ndera
Ndrae
Ndrea
Neadr
Neard
Nedar
Nedra
Nerad
Nerda
Nrade
Nraed
Nrdae
Nrdea
Nread
Nreda
aNder
aNdre
aNedr
aNerd
aNrde
aNred
adNer
adNre
adeNr
aderN
adrNe
adreN
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
eNadr
eNard
eNdar
eNdra
eNrad
eNrda
eaNdr
eaNrd
eadNr
eadrN
earNd
eardN
edNar
edNra
edaNr
edarN
edrNa
edraN
erNad
erNda
eraNd
eradN
erdNa
erdaN
rNade
rNaed
rNdae
rNdea
rNead
rNeda
raNde
raNed
radNe
radeN
raeNd
raedN
rdNae
rdNea
rdaNe
rdaeN
rdeNa
rdeaN
reNad
reNda
reaNd
readN
redNa
redaN

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

N
Na
Nad
Nade
Nader
Nadr
Nae
Naer
Nar
Nd
Nde
Nder
Ndr
Ne
Ner
Nr
a
ad
ade
ader
adr
ae
aer
ar
d
de
der
dr
e
er
r
BUILD SUCCESSFUL (total time: 0 seconds)

geek

nice and neat. harder? use tail recursion.

Joe

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.

Joe

@Nader: I just read your code, I like it!

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

nader-sleiman

rahmu wrote@Nader: I just read your code, I like it!

[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 :)

arithma

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

Joe

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.

arithma

@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.

nader-sleiman

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 :).

arithma

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

nader-sleiman

arithma wroteIf I were you I would have considered it an additional challenge.

hehe, this is never a challenge for me my friend, its a very basic exercise meant to help others probably, i need java hacking exercises (cracking+) , got some for me ??? =]