print string factorial

[jkelt46]

Hi,

Let me start off with I am not looking for someone to just post code
to solve my problem; I only want some hints.

I just started my second C programming course. My first assignment is
to create a program that takes a variable length string as input and
prints out combinations of the string without repeating characters.
The assignment I was given is:
You are given the string of cat. Create a program that outputs the
following:
cat
cta
act
atc
tca
tac

When you are testing this program the number of strings that the
program generates will be strlen(input)!. i.e. 3! = 3x2x1 = 6

What is the name of this type of program? I searched on string
factorial but the only results seem to permutation generators where
the results are 3x3x3=27 for my example. If I knew the proper term
for what I am trying to do I might be able to figure this out. Am I
trying to write a program that does combinations, factorials, or
permutations?

Thank you,

 

[Boon]

You are given the string of cat.
Create a program that outputs the following:
cat
cta
act
atc
tca
tac

i.e. every permutation of the set { c, a, t }
http://en.wikipedia.org/wiki/Permutation

Are you already familiar with recursion?

 

[nicollete]

Hi,

Let me start off with I am not looking for someone to just post code
to solve my problem; I only want some hints.

I just started my second C programming course.  My first assignment is
to create a program that takes a variable length string as input and
prints out combinations of the string without repeating characters.
The assignment I was given is:
You are given the string of cat.  Create a program that outputs the
following:
cat
cta
act
atc
tca
tac

When you are testing this program the number of strings that the
program generates will be strlen(input)!.  i.e. 3! = 3x2x1 = 6

What is the name of this type of program?  I searched on string
factorial but the only results seem to permutation generators where
the results are 3x3x3=27 for my example.  If I knew the proper term
for what I am trying to do I might be able to figure this out.  Am I
trying to write a program that does combinations, factorials, or
permutations?

Thank you,

Search for "heathfield,inner,outer" in Google archives
BTW I can see that Mr Heathfield has already replied to your query and
he will surely have to say something about this post.

 

[jkelt46]

jkelt46 said:


Presumably the assigner means "permutations". There is only one
combination of the letters "cat" because order is insignificant in
combinations. In permutations, however, it is significant.


The usual way to do this is recursive in nature. Consider the word
"cat" as a set of three (or, if you prefer, N) characters, P=0 of
which have already been placed and N-P of which are yet to be
placed.

For each set member in turn:

PERM(data, P, N)
*
if(N==P)
*
PRINT data
*
else
*
for each data member from position P onwards
*
remember where current data member is
place current data member at position P
PERM(data, P+1, N)
put current data member back where it belongs
*
*
*

Translation into C is left as an exercise. Here's the output of my
own permutation code for an input of "jkelt" (piped through fmt -60
to make it a little less vertical).

jkelt jketl jklet jklte jktel jktle jeklt jektl jelkt jeltk
jetkl jetlk jlket jlkte jlekt jletk jltke jltek jtkel jtkle
jtekl jtelk jtlke jtlek kjelt kjetl kjlet kjlte kjtel kjtle
kejlt kejtl keljt keltj ketjl ketlj kljet kljte klejt kletj
kltje kltej ktjel ktjle ktejl ktelj ktlje ktlej ejklt ejktl
ejlkt ejltk ejtkl ejtlk ekjlt ekjtl ekljt ekltj ektjl ektlj
eljkt eljtk elkjt elktj eltjk eltkj etjkl etjlk etkjl etklj
etljk etlkj ljket ljkte ljekt ljetk ljtke ljtek lkjet lkjte
lkejt lketj lktje lktej lejkt lejtk lekjt lektj letjk letkj
ltjke ltjek ltkje ltkej ltejk ltekj tjkel tjkle tjekl tjelk
tjlke tjlek tkjel tkjle tkejl tkelj tklje tklej tejkl tejlk
tekjl teklj teljk telkj tljke tljek tlkje tlkej tlejk tlekj

Thank you for the detailed answer. I believe I now understand
the problem. Part of the problem is the instructor is not a
native english speaker. He kept saying combinations and
permutations in the lecture and everyone was confused. I am
glad he gave a sample of what is wanted.

Thank you to everyone for your response. They all helped me.
I will try to write the program tonight or tomorrow.

Thanks,

 

[jkelt46]

For each set member in turn:

PERM(data, P, N)
*
  if(N==P)
  *
    PRINT data
  *
  else
  *
    for each data member from position P onwards
    *
      remember where current data member is
      place current data member at position P
      PERM(data, P+1, N)
      put current data member back where it belongs
    *
  *
*

I am sorry it took so long to post back. I had unexpected house
guests. I took a stab at solving this problem and this is what I have
come up with based on the above pseudo code:

void jpermute(char *data, int p, int n) {
int i;
char temp;

if (p == n)
printf("%s\n", data);
else {
for (i=p; i<n; i++) {
temp = data[p]; //1
data[p] = data; //2
jpermute(data, p+1, n);
data[p] = temp; //3
}
}
}

and this is my output:
abc
acc
bbc
bcc
cbc
ccc

Clearly not the correct output so I am missing something but I am not
sure what. I have tried various swap i for p and vice versa in the 3
statements but I always end with the wrong output.

Thanks,

 

[Bartc]

For each set member in turn:

PERM(data, P, N)
*
if(N==P)
*
PRINT data
*
else
*
for each data member from position P onwards
*
remember where current data member is
place current data member at position P
PERM(data, P+1, N)
put current data member back where it belongs
*
*
*

I am sorry it took so long to post back. I had unexpected house
guests. I took a stab at solving this problem and this is what I have
come up with based on the above pseudo code:

void jpermute(char *data, int p, int n) {
int i;
char temp;

if (p == n)
printf("%s\n", data);
else {
for (i=p; i<n; i++) {
temp = data[p]; //1
data[p] = data; //2
jpermute(data, p+1, n);
data[p] = temp; //3
}
}
}

and this is my output:
abc
acc
bbc
bcc
cbc
ccc

Clearly not the correct output so I am missing something but I am not
sure what. I have tried various swap i for p and vice versa in the 3
statements but I always end with the wrong output.

Try the following version. data and data[p] are exchanged, then exchanged
again after the call to jpermute to restore the original order.

It seems to work, although the permutations appear in a funny order.

void jpermute(char *data, int p, int n) {
int i;
char temp;

if (p == n)
printf("%s\n", data);
else {
for (i=p; i<n; i++) {
temp = data; //1
data = data[p]; //2
data[p] = temp; //2

jpermute(data, p+1, n);

temp = data; //1
data = data[p]; //2
data[p] = temp; //2
}
}
}

 

[CBFalconer]

.... snip ...

I am sorry it took so long to post back. I had unexpected house
guests. I took a stab at solving this problem and this is what
I have come up with based on the above pseudo code:

void jpermute(char *data, int p, int n) {
int i;
char temp;

if (p == n)
printf("%s\n", data);
else {
for (i=p; i<n; i++) {
temp = data[p]; //1
data[p] = data; //2
jpermute(data, p+1, n);
data[p] = temp; //3
}
}
}

and this is my output:
abc
acc
bbc
bcc
cbc
ccc

Clearly not the correct output so I am missing something but I
am not sure what. I have tried various swap i for p and vice
versa in the 3 statements but I always end with the wrong output.

Try the following:

--------------- File jumble.c --------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd;
wd = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main */

 

[Bartc]

I can't quite see any similarity or connection between your C code and the
algorithm you'd posted:

PERM(data, P, N)
*
if(N==P)
*
PRINT data
*

....

I'm not surprised the OP had problems implementing it.

 

[vippstar]

I can't quite see any similarity or connection between your C code and the
algorithm you'd posted:


...

I'm not surprised the OP had problems implementing it.

Fartc, read the code more carefully.

The similarity is this:

if(N == P) PRINT data

Is this part in the code:

if(unchanged < n) ...
else printf("%s\n", Perm);

In theory, == works too. In practice, using < is more secure.
Similarly, you might see that the factorial is implemented as

int i, j = 1; /* give i some value */
while(i != 0) j *= i--;

That's fine; i could be a negative number though, thus it's more
secure to simply use while(i > 0)

 

[Bartc]

The similarity is this:

if(N == P) PRINT data

Is this part in the code:

if(unchanged < n) ...
else printf("%s\n", Perm);

In theory, == works too. In practice, using < is more secure.

Have a look at the minor mods I made to the C code the OP attempted based on
the algorithm. My code also works, but is utterly different to the C code
above.

And neither code suppresses repeated characters.

 

[James Kuyper]

(e-mail address removed) said:


(Actually, Richard Heathfield wrote. The reason for distinguishing
between the two is that, in comp.lang.c, Richard Heathfield is me,
whereas Richard (with no surname) is someone else with whom I have
no desire to be confused (and I'm sure the feeling is mutual, which
is why it's rather odd that he doesn't use his surname - but then
he's a rather odd fellow).

Do you think so? I always assumed that the reason he doesn't use a
surname is that he actively enjoys the possibility of creating such
confusion. It's a pretty stupid thing to do unless that's exactly what
he wants - it's still pretty stupid even then, but less so.

 

[Dik T. Winter]

>
> The usual way to do this is recursive in nature.

I always like the following non-recursive form:

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

/* Note: will overwrite s, number should be >= 0 and < l!, where l is
the length of the string. */
void printperm(char *s, int number) {
int j, r, k;

for(j = strlen(s); j > 0; j--) {
r = number % j;
number = number / j;
k = 0;
while(r > 0 || s[k] == 0) {
if(s[k] != 0) r--;
k++;
}
putchar(s[k]);
s[k] = 0;
}
if(number != 0) printf(": permutation number out of range");
putchar('\n');
}

void perm(char *s) {
int l, i, n;
char *s1;

l = strlen(s);
if((s1 = malloc(l + 1)) == NULL) {
fprintf(stderr, "insufficient memory\n");
exit(EXIT_FAILURE);
}
n = 1;
for(i = 2; i <= l; i++) n *= i;
for(i = 0; i < n; i++) {
strcpy(s1, s); /* printperm will overwrite the string */
printperm(s1, i);
}
}

int main(void) {
perm("cat");
}

 

[vippstar]

...
 > > The assignment I was given is:
 > > You are given the string of cat.  Create a program that outputs
 > > the following:
 > > cat
 > > cta
 > > act
 > > atc
 > > tca
 > > tac
 >
 > The usual way to do this is recursive in nature.

I always like the following non-recursive form:

void perm(char *s) {
    int l, i, n;
    char *s1;

    l = strlen(s);
    if((s1 = malloc(l + 1)) == NULL) {
        fprintf(stderr, "insufficient memory\n");
        exit(EXIT_FAILURE);
    }

int main(void) {
    perm("cat");

}

I realize this is a small program and that it doesn't matter for a
single call of perm, but I also don't think it is fair to assume the
OP will be able to figure out that your function leaks memory if not
used in such trivial program.

 

[jkelt46]

(e-mail address removed) said:


(Actually, Richard Heathfield wrote. The reason for distinguishing
between the two is that, in comp.lang.c, Richard Heathfield is me,
whereas Richard (with no surname) is someone else with whom I have
no desire to be confused (and I'm sure the feeling is mutual, which
is why it's rather odd that he doesn't use his surname - but then
he's a rather odd fellow).

I am sorry about that. Sometime I remove too much.

Having got that out of the way, let's take a look at your problem:

I am sorry it took so long to post back.  I had unexpected house
guests.

Ouch. I sympathise.

I took a stab at solving this problem and this is what I
have come up with based on the above pseudo code:

void jpermute(char *data, int p, int n) {
int i;
char temp;

  if (p == n)
    printf("%s\n", data);
  else {
    for (i=p; i<n; i++) {
      temp = data[p];      //1
      data[p] = data;   //2

Here's your problem. You've just doubled up some of the data.

      jpermute(data, p+1, n);
      data[p] = temp;      //3
    }
  }
}

and this is my output:
abc
acc

Right.

<snip>

Here's one that works.

void Permute(char *Perm,
             size_t n,
             size_t unchanged)
{
  size_t outer = 0;
  size_t inner = 0;
  int temp = 0;

  if(unchanged < n)
  {
    for(outer = unchanged; outer < n; outer++)
    {
      temp = Perm[outer];

      /* NOTE: once you understand the following
         loop, you can replace it with memmove */
      for(inner = outer; inner > unchanged; inner--)
      {
        Perm[inner] = Perm[inner - 1];
      }
      Perm[unchanged] = temp;
      Permute(Perm,
              n,
              unchanged + 1);

      /* NOTE: once you understand the following loop,
         you can replace this one with memmove too */
      for(inner = unchanged; inner < outer; inner++)
      {
        Perm[inner] = Perm[inner + 1];
      }
      Perm[outer] = temp;
    }
  }
  else
  {
    printf("%s\n", Perm);
  }

}

After a quick read shouldn't temp a char?

Thanks,

 

[Dik T. Winter]

>


>
> I realize this is a small program and that it doesn't matter for a
> single call of perm, but I also don't think it is fair to assume the
> OP will be able to figure out that your function leaks memory if not
> used in such trivial program.

Indeed, I should have added a "free". But that part was a quick addition
to the basic routine which given a string and a number n, prints the n-th
permutation of that string. And that is the one I like.

 

[jkelt46]

      /* NOTE: once you understand the following
         loop, you can replace it with memmove*/
      for(inner =outer; inner >unchanged; inner--)
      {
        Perm[inner] = Perm[inner - 1];
      }

We haven't gotten to memmove yet. However I did spend the last hour
tring to figure it out. I was unsuccessful but the code you posted
with the for loops works.
I tried variations on:
memmove(&Perm[outer], &Perm[n], unchanged);
for the first for loop. I left the second loop alone.
The best output I got was:
answer = abc
answer = ac
answer =
answer =
answer = c
answer = cc

Thanks,

 

[jkelt46]

(e-mail address removed) said:

I am sorry about that.  Sometime I remove too much.

Having got that out of the way, let's take a look at your
problem:
<pseudocode snipped>
I am sorry it took so long to post back.  I had unexpected
house guests.
Ouch. I sympathise.
I took a stab at solving this problem and this is what I
have come up with based on the above pseudo code:
void jpermute(char *data, int p, int n) {
int i;
char temp;
if (p == n)
printf("%s\n", data);
else {
for (i=p; i<n; i++) {
temp = data[p];      //1
data[p] = data;   //2
Here's your problem. You've just doubled up some of the data.
jpermute(data, p+1, n);
data[p] = temp;      //3
}
}
}
and this is my output:
abc
acc
Right.
<snip>
Here's one that works.
void Permute(char *Perm,
size_t n,
size_t unchanged)
{
size_t outer = 0;
size_t inner = 0;
int temp = 0;
if(unchanged < n)
{
for(outer = unchanged; outer < n; outer++)
{
temp = Perm[outer];
/* NOTE: once you understand the following
loop, you can replace it with memmove */
for(inner = outer; inner > unchanged; inner--)
{
Perm[inner] = Perm[inner - 1];
}
Perm[unchanged] = temp;
Permute(Perm,
n,
unchanged + 1);
/* NOTE: once you understand the following loop,
you can replace this one with memmove too */
for(inner = unchanged; inner < outer; inner++)
{
Perm[inner] = Perm[inner + 1];
}
Perm[outer] = temp;
}
}
else
{
printf("%s\n", Perm);
}
}

After a quick read shouldn't temp a char?

Yes, you're probably right. It doesn't actually matter except in
some very odd circumstances that almost certainly don't apply on
your architecture (basically, sizeof(int) == 1 (making char at
least 16 bits wide) AND char is unsigned AND at least one of the
characters uses the top bit - but yes, better safe than sorry.

We are working PCs for the first half of the semester. Then we are
moving to a AXP running VMS for the second half. So code portability
is good as we will be using some of the code we wrote on the PC on the
AXP too.

Going back to the memmove for a minute. I have seen memmove examples
where in the third argument they add *sizeof(int) or *sizeof(char)
like the following:
memmove(u + 1, u, 5*sizeof(int));

Do you have to add the *sizeof? Is this one of the reasons my memmove
didn't work?

Thank you for help so far I really appreciate it.

 

[jameskuyper]

(e-mail address removed) said:

On Apr 5, 10:05 pm, Richard Heathfield <[email protected]>
wrote:
(e-mail address removed) said:

On Apr 3, 10:29 am, Richard wrote:

(Actually, Richard Heathfield wrote. The reason for
distinguishing between the two is that, in comp.lang.c, Richard
Heathfield is me, whereas Richard (with no surname) is someone
else with whom I have no desire to be confused (and I'm sure the
feeling is mutual, which is why it's rather odd that he doesn't
use his surname - but then he's a rather odd fellow).

I am sorry about that. Sometime I remove too much.
Having got that out of the way, let's take a look at your
problem:

<pseudocode snipped>

I am sorry it took so long to post back. I had unexpected
house guests.

Ouch. I sympathise.

I took a stab at solving this problem and this is what I
have come up with based on the above pseudo code:

void jpermute(char *data, int p, int n) {
int i;
char temp;

if (p == n)
printf("%s\n", data);
else {
for (i=p; i<n; i++) {
temp = data[p]; //1
data[p] = data; //2

Here's your problem. You've just doubled up some of the data.

jpermute(data, p+1, n);
data[p] = temp; //3
}
}
}

and this is my output:
abc
acc


Here's one that works.

void Permute(char *Perm,
size_t n,
size_t unchanged)
{
size_t outer = 0;
size_t inner = 0;
int temp = 0;

if(unchanged < n)
{
for(outer = unchanged; outer < n; outer++)
{
temp = Perm[outer];

/* NOTE: once you understand the following
loop, you can replace it with memmove */
for(inner = outer; inner > unchanged; inner--)
{
Perm[inner] = Perm[inner - 1];
}
Perm[unchanged] = temp;
Permute(Perm,
n,
unchanged + 1);

/* NOTE: once you understand the following loop,
you can replace this one with memmove too */
for(inner = unchanged; inner < outer; inner++)
{
Perm[inner] = Perm[inner + 1];
}
Perm[outer] = temp;
}
}
else
{
printf("%s\n", Perm);
}

}

After a quick read shouldn't temp a char?

Yes, you're probably right. It doesn't actually matter except in
some very odd circumstances that almost certainly don't apply on
your architecture (basically, sizeof(int) == 1 (making char at
least 16 bits wide) AND char is unsigned AND at least one of the
characters uses the top bit - but yes, better safe than sorry.

We are working PCs for the first half of the semester. Then we are
moving to a AXP running VMS for the second half. So code portability
is good as we will be using some of the code we wrote on the PC on the
AXP too.

Going back to the memmove for a minute. I have seen memmove examples
where in the third argument they add *sizeof(int) or *sizeof(char)
like the following:
memmove(u + 1, u, 5*sizeof(int));

Do you have to add the *sizeof? Is this one of the reasons my memmove
didn't work?

You have to tell memmove() the correct number of bytes to copy. If
sizeof(int) is greater than 1, and you want to copy 5 ints, but you
tell memmove() to only copy 5 bytes, I predict that you will be
unhappy with the result.

The expression that identifies how many bytes to copy can be written
many different ways, but will often involve sizeof(), though it's
usually best to use "sizeof expression" for some appropriate
expression rather than "sizeof(type)". For instance, if *u has the
type 'int', then it's probably best to use "sizeof *u". Excecption:
sizeof(char) is 1, so the sizeof(char) unsually both can and should be
dropped.

 

[CBFalconer]

/* NOTE: once you understand the following
loop, you can replace it with memmove*/
for(inner =outer; inner >unchanged; inner--)
{
Perm[inner] = Perm[inner - 1];
}

We haven't gotten to memmove yet. However I did spend the last
hour tring to figure it out. I was unsuccessful but the code
you posted with the for loops works.

If you are just doing a discussion of somebodies code, that is one
thing. However, if you want to print the possible words formed
from an input word, why aren't you just using the code I posted?
It is portable, standard C, and it works.

 

[jkelt46]

      /* NOTE: once you understand the following
         loop, you can replace it with memmove*/
      for(inner =outer; inner >unchanged; inner--)
      {
        Perm[inner] = Perm[inner - 1];
      }

We haven't gotten to memmove yet.  However I did spend the last
hour tring to figure it out.  I was unsuccessful but the code
you posted with the for loops works.

If you are just doing a discussion of somebodies code, that is one
thing.  However, if you want to print the possible words formed
from an input word, why aren't you just using the code I posted?
It is portable, standard C, and it works.

I am trying to write the code myself. Once I knew what I was looking
for I found about a dozen different examples on the Internet that I
could have turned in as my assignment. Some used recursion and others
iteration. However that is cheating and possibly copyright
infringement. Yes the code I turned in is similar to code that
Richard Heathfield posted, but it is not exactly the same and I
understand the code. This means I can explain what it is doing if
challenged. OK I admittedly don't understand how to replace the for
loops with memmoves but as I said we haven't gotten to that in class
yet. Why pay $$$$$ for a degree and not learn anything???

Thanks,

PS Your code looks like a nice recursive example.
PPS The assignment was due at 2PM today.