Possible Combination of String Excluding the palindromes

[soham.m17]

I want some Logical algorithm to get all possible combination of given string except the palinadromes.
Like Input is: ABC

OutPut: A,B,C,AB,AC,BC,ABC,ACB,BCA,BAC

It can't contain CBA,CAB as it already has ABC,BAC i.e reverse of those.

I want to get it done by boolean logic and but it is no where near, I guess.

public static void myComb(String s)
    {

        int num=s.length()+1;
        boolean b[]=new boolean[num];

        for(int i=(int)(java.lang.Math.pow(2, num)-4);i>0;i-=2)
        {
            String output=new String();
            for(int j=1;j<num;j++)
                if((i & (1<<j))!=0)
                {
                    System.out.print(s.substring(j-1,j));
                    //output.concat(s.substring(j,j+1));
                }
            System.out.println("");
        }
    }

[JamesCherrill]

Interesting!
Is it a requirement that it uses boolean logic like this? Could you, for example, use a recursive algorithm that would be relatively easier to code?

[phani1092]

I dont know if my idea will work out. I am giving a try.
To the output you get find out reverse of string if any reverse is found at that particular location assign to null so that we will not have a reverse in the output.

[soham.m17]

As my code goes, for the input 'abc'the output is :
bc
ac
c
ab
b
a

and for 'abcd', the output is :
bcd
acd
cd
abd
bd
ad
d
abc
bc
ac
c
ab
b
a

Which is not at all correct, as this code is considering only one sequence i.e left to right so no scope to generate 'cbd'.
So this boolean logic will not work. So can you please give me a recursive solution to this problem. I am really stuck here for 5 to 6 hours now.

[JamesCherrill]

The heart of the recursive approach is a method that takes each letter in turn and combines that with all the results of calling the same method, passing the string with that letter removed. Eg

permute ("abc") executes
   "a" + permute("bc")
   "b" + [ermute("ac")
   "c" + permute("ab")

Use another parameter to control how many chars you want in the result (call it with values from 1 to (length of input string)). Terminate the recursion when the result is long enough.
You'll then need to check for palindromic pairs by keeping a Collection of the results so far, and checking if that contains the latest result reversed (although I suspect there must be a way to avoid generating them in the first place).
It's not very elegant, but it works.

[soham.m17]

Thanks James. but it's a brute-force approach. I want a good algorithm which also keeps the time-complexity in mind.

[JamesCherrill]

Yes, I'm sure there must be a better way, but I don't know what it is!
This appears to be a homework question, so I'm sorry, but you will have to write your own code for whatever solution you prefer.

[soham.m17]

This is the code I have written in C to generate all possible combinations but this doesn't exclude the palindromes:

#include <stdio.h>


inline
void printTheArray(char *array[], int size)
{
    int index;

    for(index = 0; index < size; index++)
    {
        printf("%s ", array[index]);
    }

    printf("\n");
}

void swapStringPointers (char *stringsVector[], int i, int j)
{
    char *base;

    base = stringsVector[i];
    stringsVector[i] = stringsVector[j];
    stringsVector[j] = base;
}

void permuteWords (char *stringsVector[], int vectorSize, int processedIndex,int myLen)
{
    int currentIndex;

    if (processedIndex == myLen)
    {
        // print the vector
        printTheArray(stringsVector, myLen);
    }
    else
    {
        for (currentIndex = processedIndex; currentIndex < vectorSize; currentIndex++)
        {
            // No need to swap the same element
            if(currentIndex != processedIndex)
            swapStringPointers (stringsVector, processedIndex, currentIndex);

            permuteWords (stringsVector, vectorSize, processedIndex + 1,myLen);

            // No need to swap the same element
            if(currentIndex != processedIndex)
            swapStringPointers (stringsVector, processedIndex, currentIndex);
        }
    }
}

int main ()
{
    char *strings[] = {"A", "B","C","D"};

    int size = sizeof(strings)/sizeof(strings[0]);

    printTheArray(strings, size);
    printf("%d\n",size);

    int i;
    for(i=1;i<=size;i++)
    {
        printf("%d\n",i);
        permuteWords (strings, size, 0,i);
    }
    return 0;
}

Please help me with that.

[stultuske]

you might want to ask questions about c code in the c forum, this is the Java forum.