Permutation

A permutation is where you take a set of available choices (numbers, words,
cards, etc) and you put them together in every way possible without
repeating any. A "combination lock" is an example of a permutation (it's
actually a "permutation lock" because the numbers can't repeat.).

I am struggling to come up with the MvLogic to create such a thing. Does
anybody have any advice about creating every permutation of a set of choices
with no specific limit to the choices that might be available at a time?

...as in...

Given: A, B, C, D

Result:
A
B
C
D
AB
AC
AD
BA ... etc....
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB ...the end.



Numerically challenged,
Bill
Webnician

Permutation



Hi Webnician,

Here's a quick and dirty way to do that:

<MvASSIGN NAME = "l.allowed" VALUE = "{ miva_array_deserialize( 'a,b,c,d,e')
}" >
<MvASSIGN NAME = "l.a" VALUE = "1" >
<MvWHILE EXPR = "{ l.a LE (2 POW miva_array_max( l.allowed)) }">
<MvASSIGN NAME = "l.b" VALUE = "1" >
<MvWHILE EXPR = "{ l.b LE miva_array_max( l.allowed) }">
<MvASSIGN NAME = "l.fl" INDEX="{ l.b }" VALUE = "{
l.fl[l.b]+1 }" >

<MvIF EXPR = "{ l.fl[l.b] GT 0 }">
<MvASSIGN NAME = "l.foo" VALUE = "{ l.foo$l.allowed[l.b]$' '
}" >
</MvIF>

<MvIF EXPR = "{ l.fl[l.b] EQ (2 POW (l.b-1) ) }">
<MvASSIGN NAME = "l.fl" INDEX="{ l.b }" VALUE = "{
l.fl[l.b]*(-1) }" >
</MvIF>

<MvASSIGN NAME = "l.b" VALUE = "{ l.b+1 }" >
</MvWHILE>

<MvASSIGN NAME = "l.result" INDEX="{ l.a }" VALUE = "{ trim(l.foo) }" >
<MvASSIGN NAME = "l.foo" VALUE = "" >
<MvASSIGN NAME = "l.a" VALUE = "{ l.a+1 }" >
</MvWHILE>



Display the result:



<MvASSIGN NAME = "l.a" VALUE = "1" >
<MvWHILE EXPR = "{ l.a LE miva_array_max(l.result) }">

<MvEVAL EXPR = "{ l.a }" >: <MvEVAL EXPR = "{ l.result[l.a] }" >
<MvASSIGN NAME = "l.a" VALUE = "{ l.a+1 }" >
</MvWHILE>


I used to have a much more elegant way, using a neat and simple algorithm
(instead of the clumsy state variable l.fl) - but of course I forgot it.

Hope that helps anyway,

Markus








I've stopped 8,138 spam messages. You can too!
One month FREE spam protection at <A HREF ="http://www.cloudmark.com/spamnetsig/">http://www.cloudmark.com/spamnetsig/</A>


-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf
Of Webnician
Sent: Wednesday, February 04, 2004 12:21 PM
To: Miva Users
Subject: [meu] Permutation

A permutation is where you take a set of available choices (numbers, words,
cards, etc) and you put them together in every way possible without
repeating any. A "combination lock" is an example of a permutation (it's
actually a "permutation lock" because the numbers can't repeat.).

I am struggling to come up with the MvLogic to create such a thing. Does
anybody have any advice about creating every permutation of a set of choices
with no specific limit to the choices that might be available at a time?

...as in...

Given: A, B, C, D

Result:
A
B
C
D
AB
AC
AD
BA ... etc....
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB ...the end.



Numerically challenged,
Bill
Webnician

Permutation



I have a vague memory that it is something like
2 POW (N+1)
but I can offer you no good reason to trust my
memory ... since I myself do not.

Jack

PS: The trade-off is that this liberates me to remember
stuff the way I damn well please. Not a bad deal.

Permutation



Colleagues:

Unhappily, Markus' interesting function doesn't work uncompiled because
there is no trim() function.

But it doesn't work compiled, either. It generates 32 possible
combinations, using five elements. There should be many, many more ...
120 or even more, depending on the rules of the game.

My poor memory is being jogged.

The normal rules for permutations do not care what the ORDER of the
elements is. AB is the same as BA. If you pick up a straight poker
hand of five cards, it does not matter in what order they were dealt --
or picked up. You can rearrange them at liberty, without affecting
their significance within the game. (You can even rearrange them
ostentatiously in order to produce the impression that the hand might
actually be worth playing. But your opponents ... the swine ... will
know that all this shifting about of cards makes no practical
difference. The cards you have are the cards you have. Unfortunately,
real life is sort of like that -- though we try to defeat this fact by
ostentatiously moving the cards around whenever we get the chance.)

I believe the formula for deriving the number of possible permutations
is not the formula I suggested earlier, but rather a factorial. If you
have a deck of cards with 52 elements, the number of possible
combinations (without taking into account the order of the elements) is
enormous. In fact, it is !52, which is 8.something to the 67th power.
(The Windows calculator, for some odd reason, does not allow copying of
values from the command line; but take it from me: this is a VERY BIG
number, bigger than the computer can handle without resorting to
"scientific notation" and ending up with a negative number anyway. To
put it another way, if you deal four hands of thirteen cards from a deck
of fifty-two cards, there is a decent chance that you have dealt four
hands that have never before been dealt in the history of card-dealing.)

Now, if you are thinking about seven-card-stud -- where the order in
which you receive cards is absolutely crucial (unlike the hands of
bridge or straight poker) -- then the number of possible permutations is
much, much larger. I guess it would approach an appreciable fraction of
the number of hydrogen atoms in the earth. And this with only fifty-two
cards. Imagine pinochle!

We are still a long way from having a function that can produce the
actual arrangement of the elements of permutations of even three or four
elements.

Why, exactly, we would want to build such a function remains a mystery.
I believe that some childish but touching movie was built around the
notion of "Build it, and they will come." This idea was actually stolen
from a very famous Australian Madame who was determined to build an
elaborate whore-house in the desolate stretches of the outback. When
they asked her, Why? Her response was, "Build it, and they will come."
Her name was Lucy. Her banner slogan was "Lucy's famous outback
whore-house, where the customer always comes first!"

Jack

Permutation



Hi Jack,

You are right, only if the order doesn't matter you get 2 POW
number_of_words, for example for three words, you get 8 solutions. On the
other hand, if the order matters, there will be more, I would have probably
used the array indices of the original string and base the permutation on
that one. In that way, we'd have number_of_words+1 states (each word and
zero), and the number of combination would probably be (words+1) POW words,
so in the case of 3 words 4 POW 3 = 64.

This isn't entirely correct, because of the possible 0-state, a word on the
right side could shift left, creating potentially doubles. This is indeed
where the rules need to be clarified.

About the usage of permutations:
I did use something like my earlier solution in an old script to compare
several search terms against a list of existing (previously entered)
searches in a query cache. The idea was that if someone entered 4 search
terms, I'd compare the combination of the four words, three words, two
words, one word against the cache to see if they had been searched before.
The order did not matter in my case.

Once I found cached results, I picked the one with the smallest number of
results, and derive a more refinded search from it, or return it directly,
if the search terms are identical. I still use something similar, but in a
simplified form. It turned out ( thanks to an improved search algorithm)
that the queries are fast enough to be run again if they are not cached, so
it's not necessary to derive one query from another. Fun stuff (for some).

Markus











I've stopped 8,184 spam messages. You can too!
One month FREE spam protection at <A HREF ="http://www.cloudmark.com/spamnetsig/">http://www.cloudmark.com/spamnetsig/</A>


-----Original Message-----
From: [email protected] [mailto:[email protected]] On Behalf
Of R. Jackson Wilson
Sent: Thursday, February 05, 2004 7:22 PM
To: Markus Gieppner
Cc: 'Webnician'; 'Miva Users'
Subject: Re: [meu] Permutation

Colleagues:

Unhappily, Markus' interesting function doesn't work uncompiled because
there is no trim() function.

But it doesn't work compiled, either. It generates 32 possible
combinations, using five elements. There should be many, many more ...
120 or even more, depending on the rules of the game.

My poor memory is being jogged.

The normal rules for permutations do not care what the ORDER of the elements
is. AB is the same as BA. If you pick up a straight poker hand of five
cards, it does not matter in what order they were dealt -- or picked up.
You can rearrange them at liberty, without affecting their significance
within the game. (You can even rearrange them ostentatiously in order to
produce the impression that the hand might actually be worth playing. But
your opponents ... the swine ... will know that all this shifting about of
cards makes no practical difference. The cards you have are the cards you
have. Unfortunately, real life is sort of like that -- though we try to
defeat this fact by ostentatiously moving the cards around whenever we get
the chance.)

I believe the formula for deriving the number of possible permutations is
not the formula I suggested earlier, but rather a factorial. If you have a
deck of cards with 52 elements, the number of possible combinations (without
taking into account the order of the elements) is enormous. In fact, it is
!52, which is 8.something to the 67th power.
(The Windows calculator, for some odd reason, does not allow copying of
values from the command line; but take it from me: this is a VERY BIG
number, bigger than the computer can handle without resorting to "scientific
notation" and ending up with a negative number anyway. To put it another
way, if you deal four hands of thirteen cards from a deck of fifty-two
cards, there is a decent chance that you have dealt four hands that have
never before been dealt in the history of card-dealing.)

Now, if you are thinking about seven-card-stud -- where the order in which
you receive cards is absolutely crucial (unlike the hands of bridge or
straight poker) -- then the number of possible permutations is much, much
larger. I guess it would approach an appreciable fraction of the number of
hydrogen atoms in the earth. And this with only fifty-two cards. Imagine
pinochle!

We are still a long way from having a function that can produce the actual
arrangement of the elements of permutations of even three or four elements.

Why, exactly, we would want to build such a function remains a mystery.
I believe that some childish but touching movie was built around the notion
of "Build it, and they will come." This idea was actually stolen from a
very famous Australian Madame who was determined to build an elaborate
whore-house in the desolate stretches of the outback. When they asked her,
Why? Her response was, "Build it, and they will come."
Her name was Lucy. Her banner slogan was "Lucy's famous outback
whore-house, where the customer always comes first!"

Jack

Permutation



Wow. I'm suddenly flashing back to college Business Statistics. (wonder
where that book is...)

I guess I mislabeled what I was trying to do (not a permutation), but now
I've been inspired to apply your theories to some other projects. You guys
are damn smart.

I was able to wHack together a script for the desired effect -- to create
every "combination" from a set of words, specifically: every order possible;
without repeats; including every length of sample, up to the length of the
whole set.

Each result is fed to a custom whois Shell script to check domain name
availability. The final product will be part of a set of tools for
contracting developers (they're not too creative). Here's the tester if
anybody is interested or wants to laugh...


<mvif expr="{pdom[1] NE ''}">

<mvassign name="p" value="{1}">

<mvwhile expr="{pdom[p] NE ''}">

<mvassign name="pdom" index="{p}" value="{glosub(pdom[p],' ','')}">

<mvassign name="pmax" value="{p}">

<mvassign name="p" value="{p + 1}">

</mvwhile>

<mvassign name="vmax" value="{pmax}">

<mvassign name="p" value="{1}">
<mvassign name="v" index="{1}" value="{1}">

<mvwhile expr="{p LE pmax}">



<mvassign name="pt" value="{1}">
<mvassign name="value" value="">
<mvassign name="tdom" value="">
<mvassign name="pass" value="1">

<mvwhile expr="{pt LE pmax AND pass EQ 1}">

<mvif expr="{v[pt] IN value AND v[pt] NE 0}">
<mvassign name="pass" value="0">
</mvif>

<mvassign name="value" value="{v[pt] $ value}">

<mvif expr="{v[pt] NE 0}">
<mvassign name="tv" value="{v[pt]}">
<mvassign name="tdom" value="{pdom[tv] $ tdom}">
</mvif>

<mvassign name="pt" value="{pt + 1}">

</mvwhile>

<mvif expr="{pass EQ 1}">

<mvassign name="avail" value="_">

<mvcall action="{'<A HREF ="http://www.path.to/whois/script.shell?' $ tdom">http://www.path.to/whois/script.shell?' $ tdom</A>
$ pext}" method="GET">

<mvif expr="{'status:' CIN callvalue}">

<mvassign name="avail" value="X">

</mvif>

</mvcall>

<mveval expr="{avail}"> <mveval expr="{tdom}">


</mvif>



<mvassign name="p" value="{1}">

<mvassign name="v" index="{p}" value="{v[p] + 1}">

<mvwhile expr="{v[p] GT vmax}">

<mvassign name="v" index="{p}" value="{1}">
<mvassign name="p" value="{p + 1}">
<mvassign name="v" index="{p}" value="{v[p] + 1}">

</mvwhile>

</mvwhile>

</mvif>


- - - the end