1 reply to this topic

[BuckAMayzing]

Hi guys, I'm generating all nCr combinations of a string length n where r = n, n-1, n-2... 2

Here's what I have so far.

        private object[] getCombs(string strIn)

        {

            ArrayList list = new ArrayList();

            char[] cA = strIn.ToCharArray();

            Array.Sort(cA);

            string strArray = "";

            for (int j = 0; j < cA.Length; j++)

            {

                strArray += cA[j];

            }

            list.Add(strArray);

            


            

            list = getCombs(list, strArray.Length);

            return list.ToArray();

        }


        private ArrayList getCombs(ArrayList listIn, int iLength)

        {

            for (int i = 0; i < listIn.Count; i++)

            {

                if (listIn[i].ToString().Length < 3)

                    return listIn;

            }

            for (int i = 0; i < listIn.Count; i++)

            {

                if (listIn[i].ToString().Length == iLength)

                {

                    for (int j = 0; j < iLength; j++)

                    {

                        string temp = listIn[i].ToString().Remove(j, 1);

                        char[] cA = temp.ToCharArray();

                        Array.Sort(cA);

                        string strArray = "";

                        for (int k = 0; k < cA.Length; k++)

                        {

                            strArray += cA[k];

                        }

                        if(!(listIn.Contains(strArray)))

                            listIn.Add(strArray);

                    }

                }

                if (listIn[i].ToString().Length < iLength)

                    break;

            }


            return getCombs(listIn, iLength - 1);

        }

So, the problem lies in the fact that when I start the recursive algorithm, I have some overlap. For example:

12345 generates
1234 1235 1245 1345 2345
123 124 134 234
123 125 135 235
124 125 145 245
134 135 145 345
234 235 245 345

and then all of the 2 number combinations. I take care of the overlap with the line:

if(!(listIn.Contains(strArray)))

            listIn.Add(strArray);

but I'd like to avoid the overhead of actually generating the overlaps. Anyone have any ideas?

[BuckAMayzing]

Update: I got rid of the loop at the beginning of the recursive algorithm, and now just check the last element in the list, as it will be the shortest length string anyway. That improves performance, but it is still slow for n > 15 or so.