CODEWITHSUNDEEP
c
jay
jay

Reputation: 41

Print the combination of a string

In C, how do I print all combinations of a string?

For example: if string is "ABC" then the possible combination is A,B,C,AB,AC,BC,ABC.

I need to print all possible combination of "ABC" in console.

Upvotes: 1

Views: 2350

Answers (3)

Romeo
Romeo

Reputation: 337

What you're looking for is a backtracking algorithm.

As this is a homework, that's the place where you should start. A general idea about it is to encode the letters as integers and generate all possible combinations of length 1 using the 3 letters, then all possible combinations of length 2, and then all combinations of length 3.

Upvotes: 0

wliao
wliao

Reputation: 159

Use recursion, the idea is this:

For each recursive call, the string input is reduced by 1 character, the resulting string is stored in tmp string array. for ex:

call 1: abc

call 2: ab, last char: c

call 3: a, last char: b

then take the last char, and insert it into the list of string in tmp in all possible position, ex:

tmp contains: a, last char: b

insert b to position 0 and 1, resulting "ab" and "ba"

the result is push back to the output list, and the process continues.

pseudo-code is roughly like this:

get_perm (input):
    string[] tmp, out
    if input lengh == 1     //base case
        add input to tmp
        return tmp;

    tmp = get_permu (input[0 to input.length -1])
    char last_char = input[input.length - 1]
    //loop thru the string in tmp
    for string str in tmp:
        string tmp_str = str    //create a tmp copy
        int len = tmp_str.lengh //get the len
        //insert last_char to all possible position
        for j=0 to len:
            new_str = (add last_char to tmp_str in j position)
            out.add(new_str)

    return out

Upvotes: 0

user41871
user41871

Reputation:

Here is a hint. Think of the combinations as bit encodings. E.g.

empty = 000 = 0

C = 001 = 1

B = 010 = 2

BC = 011 = 3

A = 100 = 4

AC = 101 = 5

AB = 110 = 6

ABC = 111 = 7

Upvotes: 8

Related Questions