I take it this is an assignment? We afraid that we aren't allowed to write your assignment for you.

What have you tried so far? You should post whatever you have done and then ask specific questions about it.

What is Knuth's algorithm?

I have come up with an algorithm to do this.

Here's some pseudo code for it:

int arrayCount = 4;
char array[arrayCount + 1] = "ABCD";

int getNextPerm(char array[arrayCount + 1])
{
   static int moveArray[arrayCount] = {0};

   static int firstTime = 1;

   if (!firstTime)
   {
      firstTime = 0;

      /* Increment the moveArray
         For example: If the arrayCount
         is 3, the moveArray will go
         through the following states:
         00, 10, 20, 01, 11, 21
      */

      return FALSE;
   }

   for (int i = (arrayCount - 1), i > 0 ,i--)
   {
      // Swap the characters in positions i and moveArray[i] of the array.
   }

   return TRUE;
}

The return FALSE statement should have been conditional.

It should be:

  if (we have seen all permutations)
     return FALSE;

I have written out code for all this, but I will wait for your answer to my first question before I post it.

hi ,

this sounds just good for me . I am a math mad .
the solution to your problem based on the condition you gave : all different from one another, initially SORTED low-to-high !

[example : <given_starting_string> = "ABCFHGIED" ]
step 1 :
scan the <given_starting_string> from right to left until you catch
<right_oriented_string> that is not (SORTED HIGH-to-LOW) .
[example : <right_oriented_string>="D" , SORTED_HIGH_to_LOW(D) ? Yes => add_char .
<right_oriented_string>="ED"  ,SORTED_HIGH_to_LOW(ED) ? Yes => add_char .
                <right_oriented_string>="IED"  ,SORTED_HIGH_to_LOW(IED) ? Yes => add_char .
                <right_oriented_string>="GIED"  ,SORTED_HIGH_to_LOW(GIED) ? No => step 2 ]
step 2 : <new_char>=<last_added_char> .              [example : <new_char>="G" ]
             <tmp>=SORT_LOW_to_HIGH(<right_oriented_string>) , [example: <tmp>="DEGI" ]
             <next_char>=next_chat_after_new_char(tmp) ,[example : <next_char>="I" ]
step 3 : return(<left_oriented_string>+<next_char>+REMOVE(<tmp>,<next_char>))
            [example : return ("ABCF"+"I"+("DEGI" minus "I")) => return ("ABCF"+"I"+"DEG")]
=> ABCDFIDEG returned .

I hope this algorithm answer your question .
If that's not enough elegant for you , let me know .

Shabat Shalom .
Talmash .

sorry ,
ABCFIDEG returned .

Talmash

to mnewton:
No it is not a school assignment;  Try my website http://home.netcom.com/~dmerit/pentom/TOP.HTM

which a game I wrote for arranging puzzle pieces into a grid.  The next phase of this 'hobby' project is to conver to Javascript a C++ program I wrote long ago into that generates all possible solutions for the puzzel.  There are over 5000 solutions, not counting reflections and rotations.

Have you tested your algorithm?  I just want to know before I try to turn it into code.  Right off, I see that it does not provide an exit condition.

-- dan








 because it has the kind of simplicity that I'm looking for.  I'll

to proskig:

I had no idea that there was already a function that would do this.  I looked at the template code and it looks deceptively simple, but I'll need time to digest it.  

to Talmash:
That looks a lot like the algorithm I have.  It's all that "is it in low-to-high order" that seems somewhat clumsy (though that may be an integral part of all solutions, for all I know).

to All:
I appreciate all of your efforts!  I'll be deciding who gets the points (and looking for additional input if it comes) for a few more days before I award points.

Thanks!

to Talmash:
That looks a lot like the algorithm I have.  It's all that "is it in low-to-high order" that seems somewhat clumsy (though that may be an integral part of all solutions, for all I know).

Don't consider this a final rejection, I'd just like more time and expert input (you know, you lock out all others when you propose and answer)

-- dan

Dan,

I haven't tested my algorithm, but following through the code I wrote it looks like it should work.

It does have an exit condition, I added an addition to my last comment about it.

Anyway, here's the full code for it.

--------------
int arrayCount = 4;
char array[arrayCount + 1] = "ABCD";

int getNextPerm(char array[arrayCount + 1])
{
   static int moveArray[arrayCount] = {0};

   static int firstTime = 1;

   if (!firstTime)
   {
      firstTime = 0;

      /* Increment the moveArray
         For example: If the arrayCount
         is 3, the moveArray will go
         through the following states:
         00, 10, 20, 01, 11, 21
      */

      int done = 0;
      int index = 0;

      while (!done && (index < (X - 1)))
      {
         array[index]++;
         if (array[index] >= (X - index))
         {
             array[index] = 0;
         }
         else
         {
             done = 1;
         }

         index++;
      }

      if (!done)
      {
         // We have seen all permutations
         return 0;
      }
   }

   for (int i = (arrayCount - 1), i > 0 ,i--)
   {
      int r = moveArray[i];
      int temp = array[i];
      array[i] = array[r];
      array[r] = temp;
   }

   return 1;
}
-------------

As I said, I haven't tested, or even compiled this code, but I'm sure that the idea is solid.

If you prefer the STL solution that is fine, give the points to proskig.

Using the STL next_permutation as a template for *real* code (getting rid of all that goblety-goo about interaters and such), it turns out to implement a very elegant algorithm, indeed!

void Swap( char& c1, char& c2 ) {
  char cTmp= c1; c1=c2; c2= cTmp;
}
void Reverse( char* pFirst, char* pLast )
{
  for ( ; (pFirst != pLast) && pFirst != --pLast; pFirst++ ) {
    Swap( *pFirst, *pLast );
  }
}

bool NextPermutation(char *s, int iFirst, int iLast )
{
  int iCur= iLast;
  if ( (iFirst == iLast) || (iFirst == --iCur) ) {
    return( false );  // 1- or 0-length string: all done
  }
  while( iCur > iFirst ) {
    iCur--;
    if ( s[iCur] < s[iCur+1] ) {
      int iFindLo= iLast-1;
      while( s[iFindLo] < s[iCur] ) {
        iFindLo--;
      }
      Swap( s[iCur], s[iFindLo] );
      Reverse( &s[iCur+1], &s[iLast] );
      return( true );   // done here, but not the last
    }
  }
  return (false);     // last one
}

This is exactly what I was looking for and I coulda saved some points simply by searching MSDN -- doh!

mnewton: Alas, your code does not compile and after fixing it as best as I could (by assuming X is arraycount) it returns a few permutations, then starts repeating.

Thank you prosig, and everyone for your help!

doh!

I made another program to do this job, it actually is the retrospect algorithm, may it can give you some other idea.

#include <stdio.h>
#include <string.h>

#define STRLEN 4

int Array[STRLEN]={1,2,3,4};

#define GOT_ONE 1
#define NO_MORE 0

int GetNext()
      {
      static n = STRLEN;
      int i,j;

      n--;

      while(n >= 0 && n < STRLEN)
            {
            for (i = Array[n] + 1; i <= STRLEN; i++)
                  {
                  for (j = 0; j < n; j++)
                        {
                        if (i == Array[j])
                              break;
                        }
                  if (j == n)
                        {
                        Array[n] = i;
                        n++;
                        break;
                        }
                  }
            if (i > STRLEN)
                  {
                  Array[n] = 0;
                  n--;
                  }
            }

      if (n < 0)
            return NO_MORE;
      else
            return GOT_ONE;
      }

void Print()
      {
      for(int i=0;i<STRLEN;i++)
            printf("%d",Array[i]);
      printf("\n");
      }

void main()
      {
      int k;

      while(GetNext() == GOT_ONE)
            Print();
      }

You may assign the interger in array is the index of character in the string or anything else.

I guess I should have actually tested my code. :)  My idea was correct, I had just not written it out properly.

I know it's too late now, but here's a working version of my algorithm.


#include <string.h>
#include <iostream.h>

const int ARRAY_COUNT = 4;

int getNextPerm(char array[ARRAY_COUNT + 1])
{
    static int moveArray[ARRAY_COUNT] = {0};

    static int firstTime = 1;

    if (!firstTime)
    {
        // Increment the moveArray

        int done = 0;
        int index = 0;

        while (!done && (index < (ARRAY_COUNT - 1)))
        {
            moveArray[index]++;

            if (moveArray[index] >= (ARRAY_COUNT - index))
            {
                moveArray[index] = 0;
            }
            else
            {
                done = 1;
            }

            index++;
        }

        if (!done)
        {
            // We have seen all permutations
            return 0;
        }
    }

    firstTime = 0;

    for (int i = 0; i < (ARRAY_COUNT - 1); i++)
    {
        int index1 = (ARRAY_COUNT - i - 1);
        int index2 = moveArray[i];

        char temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    return 1;
}


int main(int argc, char* argv[])
{
    char startString[ARRAY_COUNT + 1] = "ABCD";
    char tempString[ARRAY_COUNT + 1];

    strcpy(tempString, startString);

    while(getNextPerm(tempString))
    {
        // Print out the tempString
        cout << tempString << endl;

        strcpy(tempString, startString);
    }

    return 0;
}

excellent mnewton and yz!
Completely different algorithms to do the same thing.

If you are interested in seeing the STL algorithm in action, check out:

http://home.netcom.com/~dmerit/pentsolv/pentsolv.htm 

But heed the warning on the page.  *Click cancel before 3 minutes.*  I am working of figuring out what's going on with JavaScript and could use some help... see:

http://www1.experts-exchange.com/questions/10331948/Freeze-during-long-calculation.html

if you have the time and inclination.

thanks again!
-- dan

This function cal permute strings of any lenght. It has been tested upto lenght of 6 characters.

void permute(char a[],int x,int n)
{
 char s[MAX];
 int i,j;
 char temp;
 if((n-x)==3)
 {
  for(i=x;i<n;i++)
   for(j=x;j<n-1;j++)
   {
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
    puts(a);
   }
   getch();
 }
 else
 {
  for(i=x;i<n;i++)
  {
   temp=a[i];
   a[i]=a[x];
   a[x]=temp;
   strcpy(s,a);
   permute(s,x+1,strlen(s));
  }
 }
}