permutations

[Ben Bacarisse]

Ben Bacarisse wrote:
[...]

(check: that is 4x6 = 24 permutations, i.e. 4! = 4x3x2.)

[...]

Nit: 4! = 4x3x2x1

What's the factorial and equation here?

You'll need to ask a clearer question, sorry. Someone else may know
what you are asking.

That's what I'n asking not about
encryption though that interests me too. Just an algebraic definition. I
think that's the math that uses permutations not arithmetic.

In case you want to know the definition of the function factorial:
http://mathworld.wolfram.com/Factorial.html

 

[luserXtrog]

(e-mail address removed)-berlin.de (Stefan Ram) writes:
correctly be all the permutations of the word tax?
int array[] ={ 0, 1, 2 };
  That was just written for three-letter words.
  This is more general:

Here's another general version:

Yours is slightly less general that Stefan Ram's.  Did you see how his
'main' had a loop that iterates over permutations?  His code chose to
print the permutation, but it could do anything else if it wanted to.
In your version, you have to edit the source of the jumble function to
do something other than print the permutation.

But it is more general in that we can continue to discuss it
next week.

 

[kid joe]

This is not the right algorithm.

Hi Ben,

I took this algorithm straight from Wikipedia, so it ought to be right.

There are some C issues too.

What C issues? It compiles without warnings and runs fine with me.

Please cut down your sig.

Done!

Cheers,
Joe

 

[Guest]

    What's the factorial and equation here?

If you have n items there n! permutations of them.
Where n! is defined as

Factorial n
if n = 0 or n = 1
then 1
else n x Factorial (n - 1)

or if you prefer

n! = n x (n - 1) x ... x 3 x 2 x 1

Consider 3 items and three slots the first slow has 3 choices
the second only two (one item has already been used on the first slot)
and the last only 1. Hence there are 3 x 2 x 1 = 3! = 6 ways of
arranging 3 items.

cba cab bca bac cba cab

Consider 4 items and four slots the first slow has 4 choices
the second only 3 (one item has already been used on the first slot)
etc.. Hence there are 4 x 3 x 2 x 1 = 3! = 24 ways of
arranging 4 items.

etc.

 

[Ben Bacarisse]

I took this algorithm straight from Wikipedia, so it ought to be
right.

Did you run it? The wiki algorithm uses 1-based indexes. You can't
just shift everything down because the algorithm uses the mixed-based
encoding of the permutation to generate the swaps and dividing by 2 is
not the same as dividing by 1.

for (unsigned int j = 2; j <= strlen(p); i /= j, j++)
swap(p + j - 1, p + i % j);

is one way to transcribe it into C.

What C issues? It compiles without warnings and runs fine with me.

I'd turn up the warning level. You use two inconsistent features.
Implicit int (as in 'main(int argc, char **argv)') is not permitted in
C99 but you use several C99 features (mixed declarations and
statements, long long int, declaration in a 'for' statement, no
explicit return in main). A conforming C compiler must, at least,
issue a diagnostic.

There is also the issue of strdup. This not really "a C problem" but
it means your program is POSIX with reduced portability. Regardless,
you should probably check the return from it. Personally, I'd write
it without any allocated storage.

 

[CBFalconer]

.... snip ...


Ok. I see.


/*parameter 3 of for is intellegible to me*/


I am not criticizing code here. I'm the student. I see no call to malloc
what's free for?

Look at getperm, which calls strdup, which is not defined.

 

[Leo]

[snip]

There are some C issues too.

Here's what bash's stderr told me.

p.c: In function `getperm':
p.c:15: `for' loop initial declaration used outside C99 mode
p.c: In function `main':
p.c:35: parse error at end of input

It uses C99 features (but also has incompatible C90 features).

I see the swapping in Kid's code though the main function is a little
beyond me. In particualar *++argv. I now know that if there is a pointer
in some cases like this one I think, * dereferencing is what it's called.
argv is a char ** so it must be being dereferenced. The next thing is
whats deferencing again now? I will look into it because I don't want
anyone to think I'm not looking into things myself. If I understand or
can remember what it means, I don't know. Depends on how much I would
work with it I guess.

Study it by all means, but note that the algorithm is wrong (in a minor
way) so you won't get the right answers from it.

Indeed.
When I saw a for loop starts from j = 1 and terminates at j < strlen(),
I got suspicious.