Finding by Recursion Sequences of Characters in a Char Array

Question

I have a recursion project to find all the sequences(or subsets) of a Char array as such that each character appears in the same order. For Example, for the array Char[] letters = {'A', 'B','C','D'}
The one letter sequences are "A","B","C,"D".
Two letter sequences are "AB","AC","AD","BC","BD","CD".
Three letter sequences are "ABC", "ABD","ACD","BCD"
Four letter sequence is "ABCD"

Now I thought I was on the right track with the code below, but I'm getting a lot of duplicates. I'm getting really frustrated. If anyone can point me in the right direction, I would appreciate it.

// print all subsets of the characters in s
    public static void combinations(char[] array) { combinations("", array, 0); }

    // print all subsets of the remaining elements, with given prefix 
    private static void combinations(String prefix, char[] array, int index) {

        for(int i = index; i < array.length; i++)
        {

            System.out.println(prefix + array[i]);
        }


            if (index < array.length) { 
                for(int i = index; i < array.length; i++){
                    combinations(prefix + array[i], array, index+1);
                }
            }

    }

Editting out my edit for clarification.

If this is a homework assignment, please include the homework tag. — mellamokb
– mellamokb, Commented Sep 26, 2011 at 23:04
The if statement seems redundant. The same check is already present in the for loop condition. — Mark Byers
– Mark Byers, Commented Sep 26, 2011 at 23:15
It's better to create a new question instead of changing an existing question that has already been answered. — Mark Byers
– Mark Byers, Commented Sep 26, 2011 at 23:59

Mark Byers · Accepted Answer · 2011-09-26 23:07:31Z

5

You seem to have used the wrong variable here:

combinations(prefix + array[i], array, index+1);

It should be i instead of index:

combinations(prefix + array[i], array, i+1);

Output:

A
B
C
D
AB
AC
AD
ABC
ABD
ABCD
ACD
BC
BD
BCD
CD

Ideone: http://ideone.com/H4Okw

answered Sep 26, 2011 at 23:07

Mark Byers

844k202 gold badges1.6k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Anders R. Bystrup · Accepted Answer · 2012-11-22 22:43:12Z

0

    for (int i = index; i < array.length; i++) {
        System.out.println(prefix + array[i]);
        combinations(prefix + array[i], array, i + 1);
    }

The result is:

A
AB
ABC
AC
B
BC
C

edited Nov 22, 2012 at 22:43

Anders R. Bystrup

16.1k11 gold badges65 silver badges59 bronze badges

answered Nov 22, 2012 at 22:20

Yiqing

1

Collectives™ on Stack Overflow

Finding by Recursion Sequences of Characters in a Char Array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related