[Week Eleven] Programming Contest - String Permutations

General Discussion Off Topic
1

Welcome back to week eleven of the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

This weeks challenge is to write a method (you can call it anything you want) that takes in a String and returns an array containing all the possible permutations of the given String, without repeats, so “bob” should only appear once! Additionally, no element in the array can be null

You can assume all letters are lowercase.

Examples:

perm("") -> [""]
perm(“h”) -> [“h”]
perm(“hi”) -> [“hi”, “ih”]
perm(“bob”) -> [“bob”, “bbo”, “obb”]
perm(“fun”) -> [“fun”, “fnu”, “ufn”, “unf”, “nfu”, “nuf”]
perm(“bye”) -> [“bye”, “bey”, “ybe”, “yeb”, “eby”, “eyb”]
perm(“poop”) -> [“poop”, “popo”, “ppoo”, “opop”, “oppo”, “oopp”]
perm(“stop”) -> [“stop”, “stpo”, “sotp”, “sopt”, “spto”, “spot”, “tsop”, “tspo”, “tosp”, “tops”, “tpso”, “tpos”, “ostp”, “ospt”, “otsp”, “otps”, “opst”, “opts”, “psto”, “psot”, “ptso”, “ptos”, “post”, “pots”]

Imports are allowed for this challenge!

Challenge Closes: Sunday 1/17/15

Good luck!

3

Could you post example array for ‘bob’? I’m not sure I understand conditions when word have two same letters.

4

Yeah, sorry. Completely forgot to make an example for that condition

5 
static Set<String>l;static void d(String p,String s){int n=s.length();if(n==0)l.add(p);else for(int i=0;i<n;i++)d(p+s.charAt(i),s.substring(0,i)+s.substring(i+1));}public static String[]p(String s){l=new HashSet<>();d("",s);return l.toArray(new String[0]);}

257 Chars

    static Set<String> l;

    static void d(String p, String s){
        int n = s.length();
        if (n == 0)
            l.add(p);
        else
            for (int i = 0; i < n; i++)
                d(p + s.charAt(i), s.substring(0, i) + s.substring(i+1));
    }

    public static String[] p(String s) {
        l = new HashSet<>();
        d("", s);
        return l.toArray(new String[0]);
    }
6

@Slind

Cannot resolve symbol 'l'

Looks like you forgot something here.

7

Shouldn’t perm("") return [""]?
“” is a permutation of “”, and all of the other tests have the original form as a permutation.

8

sorry forgot a line, its edited

9

That is still incorrect. For strings with duplicate characters it returns duplicate strings.

p("bob") -> ["bbo", "bbo", "bob", "bob", "obb", "obb"];

should be

p("bob") -> ["bbo", "bob", "obb"];

Use static Set<String>l=new TreeSet(); instead. It’s shorter and, being a set, it will automatically remove duplicates.

10

Based on @Slind’s method, but fixed and shorter.

Old version (257 characters):

static Set<String>o;public static String[]p(String i){o=new HashSet();p("",i);return o.toArray(new String[0]);}static void p(String p,String l){int a=l.length(),b=0;if(a>1)for(;b<a;)p(p+l.charAt(b),l.substring(0,b)+l.substring(++b));else if(a>0)o.add(p+l);}

Readable:

static Set<String> out;
public static String[] permutations(String input) {
    out = new HashSet<>();
    permutations("", input);
    return out.toArray(new String[0]);
}
private static void permutations(String prefix, String letters) {
    int length = l.length(), index = 0;
    if(length > 1) {
        for (; index < length;) {
            permutations(prefix + letters.charAt(index), letters.substring(0, index) + letters.substring(++index));
        }
    } else if (length > 0) {
        out.add(prefix + letters);
    }
}

Edited version for "" returning [""] (250 characters):

static Set<String>o;public static String[]p(String i){o=new HashSet();p("",i);return o.toArray(new String[0]);}static void p(String p,String l){int a=l.length(),b=0;if(a>1)for(;b<a;)p(p+l.charAt(b),l.substring(0,b)+l.substring(++b));else o.add(p+l);}

Readable:

static Set<String> out;
public static String[] permutations(String input) {
    out = new HashSet<>();
    permutations("", input);
    return out.toArray(new String[0]);
}
private static void permutations(String prefix, String letters) {
    int length = l.length(), index = 0;
    if(length > 1) {
        for (; index < length;) {
            permutations(prefix + letters.charAt(index), letters.substring(0, index) + letters.substring(++index));
        }
    } else {
        out.add(prefix + letters);
    }
}
11

230 Characters

public static String[]p(String s){Set<String>r=new HashSet<>();s.chars().forEach(c->Arrays.stream(p(s.replaceFirst(""+(char)c,""))).map(u->(char)c+u).forEach(r::add));return(s.isEmpty())?new String[]{""}:r.toArray(new String[0]);}

Readable version:

    public static String[] perm(String s) {
        // HashSet takes care of duplicate results
        Set<String> r = new HashSet<>();
        // For every char in the string: get the permutations of the string without that char. 
        // I simply replace the first occurence since for the permutations it does not matter WHICH occurrence of the char I remove
        s.chars().forEach(c -> Arrays.stream(perm(s.replaceFirst(""+(char) c, "")))
                     // For every permuation of the substring add the char + the permutation to the result set
                     .map(u -> (char) c + u).forEach(r::add));
        // Special case is the empty string, for which the result is the empty string - wrapped in an array
        return (s.isEmpty()) ? new String[] { "" } : r.toArray(new String[0]);
    }
1 Like
12

That test is incorrect for strings containing the same letter more than once.

13

Seeing as most people want/think perm("") should return [""] and since i agree with @jus1in, I have updated the example. If you already wrote a solution that does it the other way, both values will be accepted.

14

sorry, didn’t notice, I thought including repetitions

15

180 characters

public static String[]p(String...s){return Stream.of(s[0].split("")).flatMap(c->Stream.of(c.isEmpty()?s:p(s[0].replaceFirst(c,""))).map(u->u+c)).distinct().toArray(String[]::new);}

With whitespace:

public static String[] p(String... s) {
    return Stream.of(s[0].split(""))
            .flatMap(c ->
                    Stream.of(c.isEmpty() ? s : p(s[0].replaceFirst(c, "")))
                            .map(u -> u + c))
            .distinct()
            .toArray(String[]::new);
}

Loosely based off of @Saladoc’s answer, but very little remained the same other than the general approach.

2 Likes
16

It’s basically my approach done in a sane way. Well done.

17 
public static String[]a(String i){List<String>s=new ArrayList<>();Collections2.permutations(Chars.asList(i.toCharArray())).forEach(c->s.add(c.stream().map(Object::toString).collect(Collectors.joining())));return Iterables.toArray(s,String.class);}

247

1 Like
18

Congratulations once again to @jus1in for winning this weeks contest! And @Saladoc too I guess for his inspirational pioneering use of the holy Stream

The next challenge will be up soon

1 Like
19

I’d like to mention here that my solution was tainted by the presence of HashSet. Only @jus1in managed to bring the true glory of streams to us humble peasants. HAIL SIR JUS1IN, PROTECTOR OF STREAMS!

4 Likes