0

I am trying to write a code in Java that would allow me to take a random String like "cat" and generate all the possible letter combinations, including shorter strings.

The answers offered on the other question marked as the duplicate (Generating all permutations of a given string) don't answer this question. None of the answers include the smaller words.

For Example: c, ca, ct, cat, cta, a, ac, at, act, atc, t, ta, tc, tac, tca. ( I think that's all of them)

I have seen several answers throughout SO, but all the ones I have found reuse letters. Like ccc, cca, cct, cac, caa, cat

This answer seems to be the closest All possible words, but it allows letters to be reused. I was thinking maybe I could just modify that code to do a check of whether the character was already used, but that becomes tough with words with repeated letters, i.e. cattail.

Any and all help would be appreciated. I'll post any code if it'll help, but the link above is pretty much as far as I've gotten.

Thanks

Community
  • 1
  • 1
tjorlando
  • 75
  • 1
  • 14
  • So something like generating all permutations of a set? – awksp May 05 '14 at 03:40
  • I think so, but without repeats – tjorlando May 05 '14 at 03:41
  • Take a look at this: [Steinhaus–Johnson–Trotter algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) – awksp May 05 '14 at 03:42
  • You can fairly easily remove duplicates by running the list through a HashSet, LinkedHashSet or TreeSet before printing. – 700 Software May 05 '14 at 14:17
  • I updated the title to include the requirements you stated, these requirements which are apparently not in the suggested duplicate. I'm voting to leave open. – 700 Software May 05 '14 at 14:18
  • Duplicate combinations of letters are easily removed (I'm using a tree set at the moment), but duplicate letters I'm having a problem with. i.e. Most answers include 'ccc' if you enter the word 'cat' – tjorlando May 05 '14 at 17:48

1 Answers1

0

Here you go!

public static void printAnagrams(String prefix, String word) {
    if (word.length() <= 1) {
        System.out.println(prefix + word);
    } else {
        for (int i = 0; i < word.length(); i++) {
            String cur = word.substring(i, i + 1);
            String before = word.substring(0, i);
            String after = word.substring(i + 1);

            printAnagrams(prefix + cur, before + after);
        }
    }
}

call it like printAnagrams("", "cat")

David Xu
  • 5,555
  • 3
  • 28
  • 50
  • This is almost perfect. I can't tell if it makes smaller words too though. Getting the word cat from catfish for example, or are all the answers the same length of the original word? – tjorlando May 05 '14 at 03:57
  • Yes, all generated anagrams are the same length as the original string. – David Xu May 05 '14 at 03:59
  • I need the smaller words too, I'm afraid. I adjusted the original answer since I didn't make that clear earlier – tjorlando May 05 '14 at 04:01