[Jprogramming] permutation list

Wed Jun 27 05:50:34 HKT 2012

It is quite useful to think about what is called "The Twelvefold Way" when you're trying to enumerate these kinds of objects.

Basically, you consider enumerating all the functions between two finite sets under different conditions. Each of the sets can have labeled or unlabeled objects (ie whether order matters) and the functions can be either any function, injections (one-to-one), or surjections (onto). This gives us twelve different situations which cover most simple enumerative problems such as permutations and compositions (in the "injective functions" column), as well as the "with replacement" variations Devon mentioned earlier in this thread (in the "any function" column). The Twelvefold Way is just a handy way to unify these ideas.

Wikipedia has http://en.wikipedia.org/wiki/Twelvefold_way#Formulas, and http://mathsci.kaist.ac.kr/~drake/pdf/twelvefold-way.pdf looks quite good too. The bible is http://www-math.mit.edu/~rstan/ec/ec1.pdf (page 81). 

Notation is always a problem for these enumerative problems, Wikipedia and I prefer Knuth's http://mathdl.maa.org/images/upload_library/22/Ford/knuth403-422.pdf but it is not really standard yet. I mention this also because Iverson is credited with the first notation convention and APL is mentioned (but I think it has been referenced on the forums before). So J should be a natural choice for enumerative problems!

How much of The Twelvefold Way can we do in J? I know I've encountered several of them before, but it might be nice to try to write them all out.

-----Original Message-----
From: programming-bounces at jsoftware.com [mailto:programming-bounces at jsoftware.com] On Behalf Of Devon McCormick
Sent: Tuesday, June 26, 2012 3:54 PM
To: Programming forum
Subject: Re: [Jprogramming] permutation list

The great thing about anagram (A.) is that it allows you to work with extremely large sets without having to generate them completely.  A definition of "dyadicperm" that woirked this way would also be impressive but, looking at the looping definition of "comb", it's not apparent how one could do this.

On Tue, Jun 26, 2012 at 3:37 PM, Tirrell, Jordan (Consultant) <JTirrell at thomasnet.com> wrote:
> The mathwords.com definition from bob would be a good dyadic definition for perm. You can get there by taking all permutations of all combinations.
>
>   $3 comb 5
> 10 3
>   $perm 3
> 6 3
>   dyadicperm=: ,/@:(({~perm@#)"_1)@:comb
>   $3 dyadicperm 5
> 60 3
>
> So comb is all (ordered) x-subsets of [y].
> dyadicperm is all (with all orders) x-subsets of [y].
> (These are only the same if x is 1).
>
> I'm sure there is a better way to define it, but this is how perm should behave if it were used dyadically.
>
>
>
> -----Original Message-----
> From: programming-bounces at jsoftware.com 
> [mailto:programming-bounces at jsoftware.com] On Behalf Of bob therriault
> Sent: Tuesday, June 26, 2012 3:02 PM
> To: Programming forum
> Subject: Re: [Jprogramming] permutation list
>
> Raul,
>
> I don't think that there is a 1-1 correspondence between combinations and permutations, since each combination of items can have a number of different permutations. In the example you give the number of items is the same because the difference in the two arguments is 1, but this would not be true in the general case.
>
> I am using the definition of combination found here: 
> http://www.mathwords.com/c/combination_formula.htm
> and the formula for permutation found here: 
> http://www.mathwords.com/p/permutation_formula.htm
>
> In J the number of combinations is x!y and the number of permutations is x(!@-~ * !)y, since there are !(y-x) permutations of each combination. I guess that this would make the correspondence !(y-x) to 1.
>
> It's been a while since I sat in a combinatorics lecture, so please correct me if I have this wrong, or I am using the words in a different way than you.
>
> Cheers, bob
>
>
> -----Original Message-----
> From: programming-bounces at jsoftware.com 
> [mailto:programming-bounces at jsoftware.com] On Behalf Of Tirrell, 
> Jordan (Consultant)
> Sent: Tuesday, June 26, 2012 3:07 PM
> To: Programming forum
> Subject: Re: [Jprogramming] permutation list
>
> I don't think you'd ever want to use perm dyadically.
>
> perm=. ! A.&i. ]
>
> perm y gives all !y permutaions of y objects.
> x perm y gives the first x!y permutations of y objects.
>
> So dyadic perm is defined as the first x!y (or # x comb y) items of monadic perm. I think this is simply a consequence of the intended monadic definition.
>
>
> -----Original Message-----
> From: programming-bounces at jsoftware.com 
> [mailto:programming-bounces at jsoftware.com] On Behalf Of Raul Miller
> Sent: Tuesday, June 26, 2012 2:14 PM
> To: Programming forum
> Subject: Re: [Jprogramming] permutation list
>
> They are certainly different.
>
>   2 comb 3
> 0 1
> 0 2
> 1 2
>   2 perm 3
> 0 1 2
> 0 2 1
> 1 0 2
>
>
> In general, for n of m permutations and n of m combinations, the permutations are going to be longer (length m instead of length n).
> But the number of distinct items will be the same.
>
> --
> Raul
>
> On Tue, Jun 26, 2012 at 2:09 PM, Devon McCormick <devonmcc at gmail.com> wrote:
>> I thought that in the usual mathematical definition, combinations and 
>> permutations differ: for permutations, order matters; for 
>> combinations, it does not.  Under this definition, the combinations 
>> of
>> 3 things is just " i. 3 " - assuming we don't allow replacement?  If 
>> we do allow replacement, the permutations of 3 things are given by "
>> {3$<i.3 " and the combinations by something like " ~./:~&.>,{3$<i.3 ".
>>
>> Does this seem right?
>>
>> On Tue, Jun 26, 2012 at 12:51 PM, Raul Miller <rauldmiller at gmail.com> wrote:
>>> Note that the number of combinations and the number of permutions are the same.
>>>
>>> And, perm is just: ! A.&i. ]
>>>
>>> It seems like there ought to be a way of putting the permutations in
>>> 1 to 1 correspondence with the combinations (to give us a concise 
>>> expression for combinations).
>>>
>>> --
>>> Raul
>>>
>>> On Tue, Jun 26, 2012 at 12:41 PM, ed bierly <ebierly at gmail.com> wrote:
>>>> yes combinations not permutations
>>>> thought there might be a way that didn't loop thank you for the 
>>>> references
>>>>
>>>> On Tue, Jun 26, 2012 at 12:30 PM, R.E. Boss <r.e.boss at planet.nl> wrote:
>>>>
>>>>> 4 comb 10
>>>>>
>>>>>
>>>>> R.E. Boss
>>>>>
>>>>>
>>>>> > -----Oorspronkelijk bericht-----
>>>>> > Van: programming-bounces at jsoftware.com [mailto:
>>>>> programming-bounces at jsoftware.com] Namens ed bierly
>>>>> > Verzonden: dinsdag 26 juni 2012 18:15
>>>>> > Aan: programming at jsoftware.com
>>>>> > Onderwerp: [Jprogramming] permutation list
>>>>> >
>>>>> > what is the best way to get this list of 210 vectors?
>>>>> >
>>>>> > 4!10
>>>>> > ----------------------------------------------------------------
>>>>> > -
>>>>> > ----- For information about J forums see 
>>>>> > http://www.jsoftware.com/forums.htm
>>>>>
>>>>> ------------------------------------------------------------------
>>>>> -
>>>>> --- For information about J forums see 
>>>>> http://www.jsoftware.com/forums.htm
>>>>>
>>>> -------------------------------------------------------------------
>>>> -
>>>> -- For information about J forums see 
>>>> http://www.jsoftware.com/forums.htm
>>> --------------------------------------------------------------------
>>> -
>>> - For information about J forums see 
>>> http://www.jsoftware.com/forums.htm
>>
>>
>>
>> --
>> Devon McCormick, CFA
>> ^me^ at acm.
>> org is my
>> preferred e-mail
>> ---------------------------------------------------------------------
>> - For information about J forums see 
>> http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm

--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm