CODEWITHSUNDEEP
arraysalgorithmshuffle
arykalin
arykalin

Reputation: 403

Shuffle array several times without repeating pairs

I have a list of names, for example: "Alice", "Bob", "Steve", "Kate", "Jane", "John", "Vic", "Dan", "Robert" They call each other in a circle chain: "Alice" -> "Bob" -> "Steve" -> "Kate" -> "Jane" -> "John" -> "Vic" -> "Dan" -> "Robert" -> "Alice" I need an algorithm which will print several chains where in the result every person should have a call with all other persons without repeats. So if Vic called Dan and John called Vic yestarday all of them should have another persons in today call.

Upvotes: 0

Views: 52

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11322

Your task can be achieved by the following MiniZinc model:

include "circuit.mzn";

int: n = 9;  %  number of participants
int: rounds = 4;
set of int: N = 1..n;
set of int: Rounds = 1..rounds;

%  decision variables
array[N, Rounds] of var N: x;

predicate is_chain(array[N] of var N: c) =
  circuit(c);
  
predicate is_talking_to(N: p1, N: p2, Rounds: r) =
  (x[p1, r] == p2) \/
  (x[p2, r] == p1);
   
constraint forall(r in Rounds) (circuit([x[p, r] | p in N]));

constraint forall(r1 in Rounds, r2 in r1+1..rounds, p1 in N, p2 in p1+1..n)
  (is_talking_to(p1, p2, r1) -> not is_talking_to(p1, p2, r2));
  
function string: show_chain(array[N] of var N: c) =
  join(" -> ", [ "\(c[p])" | p in N ]) ++ " -> \(c[1])\n";
  
output [ show_chain([fix(x[p, r]) | p in N]) | r in Rounds ];

Example output:

7 -> 5 -> 2 -> 9 -> 8 -> 4 -> 3 -> 6 -> 1 -> 7
4 -> 8 -> 9 -> 7 -> 1 -> 5 -> 2 -> 3 -> 6 -> 4
6 -> 9 -> 1 -> 3 -> 7 -> 2 -> 8 -> 4 -> 5 -> 6
2 -> 4 -> 6 -> 5 -> 3 -> 7 -> 9 -> 1 -> 8 -> 2

For more than four rounds, no solution was found.

The model interpretes to "have a call" as symmetric "speaking to eachother". It does not matter, who is initiating a call.

Upvotes: 1

Related Questions