permutation - question simplified and clarified.

[shed...@gmail.com]

Sorry about the duplicate post, but I realized my last question was a bit over complicated.

 

Is there an ampl command that will display all permutations of a set ?

 

 

set available = [avail1, avail2, avail3, avail4, avail5 avail6, avail7, avail8]

[Robert Fourer]

There are 8! = 40,320 permutations of 8 set members.  The only way I can see to generate them all in an AMPL script is with 8 nested loops,

 

   for {i1 in available}

     for {i2 in available diff {i1}}

       for {i3 in available diff {i1,i2}}

         for ...

 

but I think this would be very slow.  Maybe another reader can think of a better approach.

 

Bob Fourer

am...@googlegroups.com

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Meketon, Marc]

I don’t know if this will help…  There is a decent Wikipedia article that discusses algorithms for generating all permutations: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

---

This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation.

[charles shedrick]

Thanks Bob, so if I indicated that that order was not important (i.e., unordered) and  no repetition allowed.

n! /(n-r)!(r!) for n= 8 and r =2 should only display all 36 subsets of 2? insteard of the 40,320. is the nested loop still the best approach ?

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/qsqjdnaVLXs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

[fbahr]

An AMPL implementation of QuickPerm -- which, IMHO, performs reasonably well.

set available ordered;
# w/ data;
#    set available := avail1 avail2 avail3 avail4 avail5 avail6 avail7 avail8;

param N = card(available);
param sym {k in 0 .. N-1} symbolic := member(k+1,available);
param idx {k in 0 .. N-1} default k;
param p   {k in 0 .. N-1} default 0;
param k                   default 1;
param l;
param swap;

set permutations {0 .. (prod {f in 1 .. N} f)-1};
let permutations[0] := available;
param count default 1;

repeat while k < N {
  if p[k] < k then {
    let l := if k mod 2 == 0 then 0 else p[k];
    let swap   := idx[k];
    let idx[k] := idx[l];
    let idx[l] := swap;
    let permutations[count] :=  union {s in (setof {i in 0 .. N-1} idx[i])} { sym[s] };
    let count := count + 1;
    let p[k] := p[k] + 1;
    let k := 1;
  }
  else {
    let p[k] := 0;
    let k := k + 1;
  }
};

# display permutations


My initial impression, though, was that you were more looking for power set -- which can be done like:

set SS := 1 .. 2**card(available)-1;
set POW {k in SS} := setof {a in available: (k div 2**(ord(a)-1)) mod 2 = 1} a;

# display POW;


--fbahr

[fbahr]

> ... n! /(n-r)!(r!) for n= 8 and r =2 should only display all 36 subsets of 2

{8 choose 2} [= _28_] elements can be easily computed as

1. set of tuples

set pairs := setof {i in available, j in available: ord(i) < ord(j)} (i,j);

or as

2. indexed set

param N := card(available);
param M := ( prod { n in 1 .. N } n ) / ( 2 * prod { n in 1 .. N - 2 } n );
set pairs { 1 .. M };
let {i in available, j in available: ord(i) < ord(j) } pairs[(ord(i)*(ord(i)-1))/2 + ord(j) - 1] := { i, j };

--fbahr

[shed...@gmail.com]

Thanks so much that was a huge help. 

 I think that will work, but I omitted a slight curve in the program.

The avail1, avail2...avail8 are actually matrices. Is there a clever or simple way to map the matrices to set or indexing scheme so I can manipulate the sets matrix sets? I've tried a few loops but I can't quite get it. I can get it to work the long way, but it does not scale well at all.  I basically have to drop and restore the matrices. as you can see from the question and example below that if I did it under my current method I'd have to figure out every matrix combination to tell ampl which "sets of matrices" to drop and restore. The only way I can get the correct matrix mixed[e.j] is to constraint it over multiple matrices as follows.  

param avail1 {e in LINK, j in CHANNEL};

param avail2 {e in LINK, j in CHANNEL};

param avail3 {e in LINK, j in CHANNEL};

param avail4 {e in LINK, j in CHANNEL};

subject to total1{e in LINK}: S <= sum {j in CHANNEL}(mixed[e,j]* avail1[e,j]);

subject to total2{e in LINK}: S <= sum {j in CHANNEL}(mixed[e,j]* avail2[e,j]);

subject to total3{e in LINK}: S <= sum {j in CHANNEL}(mixed[e,j]* avail3[e,j]);

subject to total4{e in LINK}: S <= sum {j in CHANNEL}(mixed[e,j]* avail4[e,j]);

[Robert Fourer]

For the param and subject to statements that you give, the same thing could be written more concisely using one more indexing set. For example;

param nAvail = 4;
param avail {1..nAvail, LINK, CHANNEL};

subject to total {i in 1..nAvail, e in LINK}:
S <= sum {j in CHANNEL} mixed[e,j]* avail[i,e,j];

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of shed...@gmail.com
Sent: Sunday, March 23, 2014 12:52 PM
To: am...@googlegroups.com

[charles shedrick]

Thanks Bob. After staring at problem for a week I realized my error looking back at me. I only needed 2 subscripts for my first variable instead of all three.

[charles shedrick]

I'm not sure if I solver issue ot if it's my formulation, but seem to be missing sets here.

 

for example if N := 4 I should get 6 pairs but I'm only getting 5 ?

[fbahr]

My mistake, poor math skills.

This works as intended:

param N = card(available);
param M = N*(N-1)/2;

set pairs { 1 .. M };

let {i in available, j in available: ord(i) < ord(j) } pairs[(ord(i)-1)*(N-ord(i)/2) + ord(j) - ord(i)] := { i, j };

--fbahr

[charles shedrick]

Thanks florian. If my math skills were any better I would've been able to figure out how to fix the index problem. pretty neat calculation.  Is that a pretty standard way to index permutations or did you customize it based on my question. pairs 1, pairs 2...

[fbahr]

On Wednesday, April 2, 2014 9:29:35 PM UTC+2, charles shedrick wrote:

Thanks florian. If my math skills were any better I would've been able to figure out how to fix the index problem. pretty neat calculation.  Is that a pretty standard way to index permutations or did you customize it based on my question. pairs 1, pairs 2...

Well, I'd say: "somehow" standard.

If we want to calculate

M := nchoosek(N,2) = ( prod { n in 1 .. N } n ) / ( 2 * prod { n in 1 .. N - 2 } n ) = N*(N-1)/2

pairs <i,j> (with i < j), and add them sequentially to an array, the insertion point can be calculated as

( sum { elems in 1 .. ord(i)-1 } ( N - elems ) ) + ( ord(j) - ord(i) )

[...which, at first glance, might look a bit more complicated than it actually is.

To make things more "graphic", think of N = 4:

Col.    1    2   3
------+--------------
Row 1 | 1,2  2,3  3,4
    2 | 1,3  2,4       <- pairs <i,j> for N=4
    3 | 1,4
------+--------------
#elems  3    2    1

then: N-elems corresponds to the number of elements in column ord(i)-1 [i. e., the sum expression computes the number of elements in all columns < ord(i)], and ord(j)-ord(i) is the row index in column ord(i).

For instance <2,4>: 4-1 = 3 elements in column 1, row index 4 - 2 = 2; i. e., insertion point (array) = 3 + 2 = 5.]

And finally, we can transform the sum expression to a closed-form expression using the Gaussian sum formula.

--fbahr

P.S.: Alternatively, we could "compute" the insertion poing just by incrementing an index parameter:

param idx default 0;
for { i in available, j in available: ord(i) < ord(j) } {
  let idx := idx + 1;
  let pairs[idx] := { i, j };
}