/* Party mixing in Picat. Based on a real problem: 27 people sits at 4 tables and shall be mixed in some way. What is the optimal mixing so a person will talk with as many different people as possible? (Thanks Simon!) Here are three models with some common assumptions: - There are NumTables tables and NumAtTables chairs at each table - There is exactly one _empty chair_ which is the chair that is used in each move: each person move to the empty chair, and thus a new chair will be available (be a new empty chair). The number of moves is thus NumTables*NumAtTables - 1. - The main constraint is that a person must move from one table to another table. After all people has moved, no one will sit at his/her original table. However, we don't care about the exact position at the table, i.e. there is no constraint that forbids that to former neighbours from table 1 will sit together at table 4. party_mixing/4 and party_mixing3/3 now requires that the new _immediate neighbours_ (to the left and right) is not from the same original table. This is only valid for > 2 tables. - All models use random heuristics (in solve/1) to make the moves more random looking. The three models are * party_mixing/4: simple approach Tested with go/0. - generate a final setting and figure out the moves This is quite fast, see below. * party_mixing2/5: explicitly generate each step Tested with go2/0. The advantage of having each move explicit is that we can add detailed constraints such as: * The first move should be from the first table, the second move from the second table and so on. This will make the model faster (symmetry breaking). * A move will not be from the same table as the previous table. (This constraint is harder to state in party_mixing/4.) * party_mixing/3: This is a simplification of party_mixing/4 where only the circuit (the list L) is used, i.e. the matrix (X) is not used. For presentation, the moves (path) is extracted by circuit_path/2 and the matrix is just the 2D version of L. Some timings: Tables Chairs Total Chairs party_mixing/4 CP party_mixing2/5 CP party_mixing/4 SAT ------------------------------------------------------------------------------------------------------------- 4 7 28 0.0s 0.02s 2.572s 10 7 70 0.008s 0.024s >3min 14 17 238 0.16s 12.547s - 24 10 240 0.156s 16.161s - 2(*) 300 600 2.454s > 1min - 300 2 600 2.434s > 1min - 24 27 648 2.84s RAM exhausted - 40 30 1200 17.609s - - 40 40 1600 42.983s - - 500 4 2000 94.025s - - (party_mixing3/3 has the same times as party_mixing/4.) (*) For NumTables <= 2 we skip the constraint that the target table must be different for the immediate neighbours (since it's impossible). Exactly one free chair and possible decompositions --------------------------------------------------- A note regarding the assumption of one free chair. Both models assumes that there is exactly one free chair at any move. This mean that we will use N+1 chairs. However, the total number of people (N+1) may not be decomposed exactly in NumTables * NumAtTables. As shown in go4/0, all N > 2 where N+1 is not a prime number are decomposable in this manner, often in more than one ways. Examples: - N = 27 2 tables x 14 chairs -1 = 27 4 tables x 7 chairs -1 = 27 7 tables x 4 chairs -1 = 27 14 tables x 2 chairs -1 = 27 - N = 35 Tables Chairs 2 18 3 12 4 9 6 6 9 4 12 3 18 2 For N+1 is a prime there is no decomposition. What we can do the is to add one chair - using a dummy person - which is used in the same way as all the other people/chairs. The move for this person will be an empty move which may be immediately followed by a real move. N+1 is a prime: - N = 28 28 is a prime - 1. Hence we use N = N+1 = 29 instead. Tables Chairs 2 15 3 10 5 6 6 5 10 3 15 2 Another way of fixing this is to let one person, e.g. the host, be outside the moving and use N chairs (with one empty chairs) as planned. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import cp. % import sat. % much slower main => go. % % party_mixing/4 % % Here is a simple solution which satisfy the constraints % that each person at the end will sit at another table. % % But it's quite silly since it's just moving most % people from one table to another. % % 8 9 10 11 12 13 14 % 2 3 4 5 6 7 15 % 22 23 24 25 26 27 28 % 16 17 18 19 20 21 1 % % % Using the "rand" (rand_var + rand_val) search heuristic % give a much better solution: % % End result % 24 18 10 15 25 11 26 % 20 27 2 19 28 17 4 % 9 22 14 6 8 23 1 % 12 21 5 13 3 16 7 % % End result (original table) % 4 3 2 3 4 2 4 % 3 4 1 3 4 3 1 % 2 4 2 1 2 4 1 % 2 3 1 2 1 3 1 % % Move 1: person 24 move to pos 1, from table 4 to table 1 % Move 2: person 5 move to pos 24, from table 1 to table 4 % Move 3: person 25 move to pos 5, from table 4 to table 1 % Move 4: person 13 move to pos 25, from table 2 to table 4 % Move 5: person 17 move to pos 13, from table 3 to table 2 % Move 6: person 14 move to pos 17, from table 2 to table 3 % Move 7: person 4 move to pos 14, from table 1 to table 2 % Move 8: person 15 move to pos 4, from table 3 to table 1 % Move 9: person 9 move to pos 15, from table 2 to table 3 % Move 10: person 27 move to pos 9, from table 4 to table 2 % Move 11: person 16 move to pos 27, from table 3 to table 4 % Move 12: person 22 move to pos 16, from table 4 to table 3 % Move 13: person 12 move to pos 22, from table 2 to table 4 % Move 14: person 28 move to pos 12, from table 4 to table 2 % Move 15: person 7 move to pos 28, from table 1 to table 4 % Move 16: person 26 move to pos 7, from table 4 to table 1 % Move 17: person 3 move to pos 26, from table 1 to table 4 % Move 18: person 10 move to pos 3, from table 2 to table 1 % Move 19: person 2 move to pos 10, from table 1 to table 2 % Move 20: person 18 move to pos 2, from table 3 to table 1 % Move 21: person 6 move to pos 18, from table 1 to table 3 % Move 22: person 11 move to pos 6, from table 2 to table 1 % Move 23: person 19 move to pos 11, from table 3 to table 2 % Move 24: person 8 move to pos 19, from table 2 to table 3 % Move 25: person 20 move to pos 8, from table 3 to table 2 % Move 26: person 23 move to pos 20, from table 4 to table 3 % Move 27: person 21 move to pos 23, from table 3 to table 4 % % (There are just 27 moves since there are only 27 people + 1 empty chair.) % go => garbage_collect(200_000_000), NumTables = 4, NumAtTables = 7, NumPeople = NumTables*NumAtTables, println([numTables=NumTables,numAtTables=NumAtTables,numPeople=NumPeople]), party_mixing(NumTables,NumAtTables, X,L), print_moves(NumTables,NumAtTables,X,L), nl. % % Checking for a specific N with different % configuration of tables and chairs. % % Different configurations of the same N % will have different solve times. % % For N = 701: % [n = 701,numTables = 2,numAtTables = 351] % CPU time 7.456 seconds. Backtracks: 0 % % [n = 701,numTables = 3,numAtTables = 234] % CPU time 4.86 seconds. Backtracks: 0 % % [n = 701,numTables = 6,numAtTables = 117] % CPU time 4.517 seconds. Backtracks: 0 % % [n = 701,numTables = 9,numAtTables = 78] % CPU time 4.732 seconds. Backtracks: 0 % % [n = 701,numTables = 13,numAtTables = 54] % CPU time 4.516 seconds. Backtracks: 0 % % [n = 701,numTables = 18,numAtTables = 39] % CPU time 4.268 seconds. Backtracks: 0 % % [n = 701,numTables = 26,numAtTables = 27] % CPU time 4.373 seconds. Backtracks: 0 % % [n = 701,numTables = 27,numAtTables = 26] % CPU time 4.284 seconds. Backtracks: 0 % % [n = 701,numTables = 39,numAtTables = 18] % CPU time 4.44 seconds. Backtracks: 0 % % [n = 701,numTables = 54,numAtTables = 13] % CPU time 4.404 seconds. Backtracks: 0 % % [n = 701,numTables = 78,numAtTables = 9] % CPU time 4.421 seconds. Backtracks: 0 % % [n = 701,numTables = 117,numAtTables = 6] % CPU time 4.424 seconds. Backtracks: 0 % % [n = 701,numTables = 234,numAtTables = 3] % CPU time 4.54 seconds. Backtracks: 0 % % [n = 701,numTables = 351,numAtTables = 2] % CPU time 4.609 seconds. Backtracks: 0 % % Running some more tests, it seems that the first configuration, % i.e. using the least amount of tables, is slowest and then the % other configurations are about the same time. % However, this needs to be checked more... % go1 => garbage_collect(200_000_000), N = 500, if prime(N+1) then printf("N (%d) is a prime - 1. We use N+1 (%d) chairs instead.\n", N,N+1), N := N + 1 end, printf("N = %d. We will use N+1 (%d) chairs\n", N,N+1), All= find_all([NumTables,NumAtTables],get_config(N, NumTables,NumAtTables)), println(all=All), foreach([NumTables,NumAtTables] in All) println([n=N,numTables=NumTables,numAtTables=NumAtTables]), time2(party_mixing(NumTables,NumAtTables, _X,_L)), % print_moves(NumTables,NumAtTables,X,L), nl end, nl. % % A more elaborate CP model: party_mixing2/5 % % Here is the original problem with 4 tables and 7 people at % each table. The free chair is the last chair at the last % table (position 28) % % 1 2 3 4 8 9 10 11 % 5 6 7 12 13 14 % % 15 16 17 18 22 23 24 25 % 19 20 21 26 27 _ % % The 28'th chair is empty, and it will be the target of the each move. % go2 => nolog, garbage_collect(200_000_000), NumTables = 14, NumAtTables = 17, NumPeople = NumTables*NumAtTables, println([numTables,numAtTables,numPeople=NumPeople]), party_mixing2(NumTables,NumAtTables, X,Moves,Z), println("'-' marks the empty chair which indicates the next move"), foreach(M in 2..Z) {Person,FromTable,ToTable} = Moves[M], printf("Move %2d: person %2d move from table %2d to table %d\n",M-1,Person,FromTable,ToTable), foreach(Row in X[M]) foreach(R in Row) if R == NumTables*NumAtTables then print(" - ") else printf("%3d ", R) end end, nl end, nl end, % println(moves=Moves), println(z=Z), nl. % % Benchmark the two versions % % go3 => Benchmark = [ [4,7], [10,7], [14,17], [24,10], [2,300], [300,2], [24,27], [40,30], [40,40] ], foreach([NumTables,NumAtTables] in Benchmark) garbage_collect(250_000_000), NumPeople = NumTables*NumAtTables, println([numTables=NumTables,numAtTables=NumAtTables,numPeople=NumPeople]), println("party_mixing/4"), flush(stdout), time2(party_mixing(NumTables,NumAtTables, _X,_L)), flush(stdout), % println("party_mixing2"), % time2(party_mixing2(NumTables,NumAtTables, _X2,_Moves2,_Z2)), % garbage_collect(250_000_000), % println("party_mixing3/3"), % flush(stdout), % time2(party_mixing3(NumTables,NumAtTables, _L2)), % flush(stdout), nl, flush(stdout) end, nl. % % Get all the possible configurations given the number of people at % the party (N). This works for all N where N+1 is not a prime (of course % since there is no decomposition of a prime number). % % No solutions: [4,6,10,12,16,18,22,28,30,36,40,42,46,52,58,60,66,70,72,78,82,88,96,100] % % However, it seems that for all these NoSolution numbers there are % solutions for N-1 and N+1. % % For N where N+1 is a prime, there is a trivial solution: % NumTables = 1 and NumAtTables = N+1 % However, is not appropriate for the party_mixing problem % since the requirement is that all must change table... % % As mentioned in the presentation above, it's easy to use N+1 chairs % instead and let one chair be a dummy chair. % Another way is to use N-1 chairs and let one person, e.g. the host, % not to be moved at all. Note: This chair will not be in the % configuration. % go4 => NoSolutions = [], foreach(N in 3..100) println(n=N), All= find_all([NumTables,NumAtTables],get_config(N, NumTables,NumAtTables)), if All != [] then foreach(A in All) println(A) end else NoSolutions := NoSolutions ++ [N], printf("For N=%d there is no solution!\n", N), if get_config(N-1,_,_) then printf("However, there's a solution for N-1 (%d)\n", N-1) else printf("There is NOT a solution for N-1 (%d)\n", N-1), halt end, if get_config(N+1,_,_) then printf("However, there's a solution for N+1 (%d)\n", N+1) else printf("There is NOT a solution for N+1 (%d)\n", N+1), halt end end, nl end, println(no_solutions=NoSolutions), nl. % % Even simpler model. % Compared to party_mixing/4, party_mixing3/3 just use the list L, % i.e. skipping the matrix X completely. % go5 => garbage_collect(200_000_000), NumTables = 40, NumAtTables = 30, NumPeople = NumTables*NumAtTables, println([numTables=NumTables,numAtTables=NumAtTables,numPeople=NumPeople]), party_mixing3(NumTables,NumAtTables,L), println(l=L), % convert to the path circuit_path(L,Path), println(path=Path), % convert to matrix X = { { L[(I-1)*NumAtTables + J] : J in 1..NumAtTables } : I in 1..NumTables}, % print_moves(NumTables,NumAtTables,X,L), nl. % % Print the moves from party_mixing/5 % print_moves(NumTables,NumAtTables,X,L) => NumMoves = NumTables*NumAtTables, println("Start:"), foreach(I in 1..NumTables) foreach(J in 1..NumAtTables) printf("%3d ", (I-1)*NumAtTables + J) end, nl end, nl, println("End result"), foreach(Row in X) foreach(R in Row) printf("%3d ", R) end, nl end, nl, println("End result (original table)"), foreach(Row in X) foreach(R in Row) printf("%3d ", 1+((R-1) div NumAtTables)) end, nl end, nl, % The empty chair is at place 1 and then move from there... Chair = 1, foreach(M in 1..NumMoves-1) element(Chair,L,Pos), TableTo = get_table(Chair,NumAtTables), TableFrom = get_table(Pos, NumAtTables), printf("Move %3d: person %3d move to pos %3d, from table %3d to table %3d\n",M,Pos,Chair,TableFrom,TableTo), Chair := Pos end, nl, % alternative variant using circuit_path/2 Path = new_array(NumMoves), circuit_path(L,Path), println("Summary (by Path):"), println( to_string(Path[1]) ++ "->1, " ++ [to_string(Path[I+1]) ++ "->" ++ to_string(Path[I]) : I in 1..NumMoves-2].join(", ")), nl. % % Get table/chairs configurations for N people. % get_config(N, NumTables,NumAtTables) => NumTables :: 1..N, NumAtTables :: 1..N, NumTables * NumAtTables - 1 #= N, % NumTables #<= NumAtTables, solve($[],[NumTables,NumAtTables]). % % Return the table for position N % get_table(N,NumAtTables) = 1+(N-1) div NumAtTables. % % party_mixing/4 % % A simple and fast approach. % % Generate the end result (i.e. after NumTables*NumAtTables moves) % and then figure out the moves. % % The constraints/assumptions: % % - empty chair at position 1 % % - each person move exactly one time % % - a person should not end at the same table he/she % was originally placed. % % - there should be sub loops % This is a very important thing: We must be sure % that all peple can be moved in order. % % The global constraint circuit/1 handle this and it is % one of the main reason for the speed of this model. % Compare with TSP problems where the circuit/1 constraint % is used. % % - if there is more than 2 tables: % the end place for a person must not be immediate left or right % of a person from the same original table. % % - the rand_val heuristic is used for a random looking result % party_mixing(NumTables,NumAtTables, X,L) => NumPeople = NumTables*NumAtTables, X = new_array(NumTables,NumAtTables), X :: 1..NumPeople, L = X.vars(), % all_different(L), % slightly faster without foreach(I in 1..NumTables, J in 1..NumAtTables) % ensure that people that starts at table T don't stays at the same table (1+((X[I,J]-1)) div NumAtTables) #!= (1+(((I-1)*NumAtTables+J)-1) div NumAtTables), % Ensure that two neighbours from the same table will not sit beside each other % in the new configuration. % Note that for N <= 2 this will give no solution, so the constraint is ignored. if NumTables > 2 then if J > 1 then 1+(X[I,J-1]-1) div NumAtTables #!= 1+(X[I,J]-1) div NumAtTables end, if J < NumAtTables then 1+(X[I,J+1]-1) div NumAtTables #!= 1+(X[I,J]-1) div NumAtTables end end end, % There should be no sub circuits (sub loops). % (It also constrain the values to be different.) circuit(L), % % Search % _ = random2(), % indeterministic random println(solve), solve([rand_var,rand_val],L). % % party_mixing2/5 % party_mixing2(NumTables,NumAtTables, X,Moves,Z) => TotalPlaces = NumTables*NumAtTables, NumMoves = TotalPlaces, FreeChair = NumTables*NumAtTables, % the empty chair % % decision variables % % places for each person at each move X = new_array(NumMoves,NumTables,NumAtTables), X :: 1..TotalPlaces, XVars = X.vars(), % the moves: [Person,TableFrom,TableTo] % i.e. person Person move from table TableFrom to TableTo Moves = new_array(NumMoves,3), Moves :: 1..TotalPlaces, % inits % init first table configuration foreach(I in 1..NumTables, J in 1..NumAtTables) X[1,I,J] #= (I-1)*NumAtTables + J end, % first move (dummy move) Moves[1,1] #= 1, Moves[1,2] #= 1, Moves[1,3] #= 1, % restrict the domains of the Table entries in Moves foreach(M in 1..NumMoves) Moves[M,2] #<= NumTables, Moves[M,3] #<= NumTables end, % objective: maximum the number of people at different table compared with the start position % % note: there is no real objective: we do NumTables*NumAtTables moves % % Number of different tables Z #= sum([ (1+((X[NumMoves,I,J]-1)) div NumAtTables) #!= (1+(((I-1)*NumAtTables+J)-1) div NumAtTables) : I in 1..NumTables, J in 1..NumAtTables]), Z #= NumMoves, % all people have moved % println(z_before=Z), % all moves are just permutations foreach(M in 1..NumMoves) all_different($[X[M,I,J] : I in 1..NumTables, J in 1..NumAtTables]) end, % must move different persons each time all_different($[Moves[M,1] : M in 2..NumMoves]), % the first table must be moved from first, then table 2, table 3, etc to NumTables foreach(I in 2..min(NumTables+1,NumMoves)) Moves[I,2] #= I-1 end, % do the moves... foreach(M in 2..NumMoves) % exactly two positions are changed each move: % FreeChair <-> the selected person's old chair sum($[X[M-1,I,J] #!= X[M,I,J] : I in 1..NumTables,J in 1..NumAtTables]) #= 2, % the previous and current move XFrom = [X[M-1,I,J] : I in 1..NumTables,J in 1..NumAtTables], XTo = [X[M,I,J] : I in 1..NumTables,J in 1..NumAtTables], % get the position of the FreeChair (PosFrom) of the previous config % and the position to move to (PosTo) element(PosFrom,XFrom,FreeChair), element(PosTo, XFrom,Person), % identify the tables % it should be a move between different tables TableFrom #= 1+(PosFrom-1) div NumAtTables, TableTo #= 1+(PosTo-1) div NumAtTables, if M > 2 then % M = 1 is a dummy move so we skip this TableFrom #!= TableTo end, % swap the positions to move from (to FreeChair) element(PosFrom,XTo,Person), element(PosTo, XTo,FreeChair), % don't move from the same table twice in a row, (for diversity) % if M > 2 then % Moves[M,2] #!= Moves[M-1,2], % FromTable % Moves[M,3] #!= Moves[M-1,3] % ToTable % % , Moves[M,2] #!= Moves[M-1,3] % end, Moves[M,1] #= Person, Moves[M,2] #= TableTo, Moves[M,3] #= TableFrom end, println(solve), Vars = Moves.vars() ++ XVars, % Vars = XVars ++ Moves.vars(), % _ = random2(), solve($[rand_val],Vars). % % A variant of party_mixing/4, where just the single list L % is used for the circuit. % The moves (path) must be revealed with circuit_path/2. % party_mixing3(NumTables,NumAtTables, L) => NumPeople = NumTables*NumAtTables, L = new_array(NumPeople), L :: 1..NumPeople, % all_different(L), % slightly faster without foreach(I in 1..NumTables, J in 1..NumAtTables) K = (I-1)*NumAtTables + J, % ensure that people that starts at table T don't stays at the same table 1+((L[K]-1) div NumAtTables) #!= 1+(((I-1)*NumAtTables+J)-1) div NumAtTables, % Ensure that two neighbours from the same table will not sit beside each other % in the new configuration. % Note that for N <= 2 this will give no solution, so the constraint is ignored. if NumTables > 2 then if J > 1 then 1+((L[K-1]-1) div NumAtTables) #!= 1+(L[K]-1) div NumAtTables end, if J < NumAtTables then 1+((L[K+1]-1) div NumAtTables) #!= 1+(L[K]-1) div NumAtTables end end end, % There should be no sub circuits (sub loops). % It also constrain the values to be different. circuit(L), % % Search % _ = random2(), % indeterministic random println(solve), solve([rand_var,rand_val],L). % % In this model we used circuit_path/2 only % for presentation so the all_different/1 % constraints can be skipped... % circuit_path(X,Z) => N = length(X), Z = new_array(N), Z :: 1..N, % % The main constraint is that Z[I] must not be 1 % until I = N, and for I = N it must be 1. % all_different(X), all_different(Z), % put the orbit of x[1] in in z[1..n] X[1] #= Z[1], % when I = N it must be 1 Z[N] #= 1, % Redundant constraint. It is covered by the constraints % X[N] = 1 and alldifferent. % foreach(I in 1..N-1) Z[I] #!= 1 end, % % Get the orbit for Z. % foreach(I in 2..N) element(Z[I-1],X,Z[I]) end.