# Tag Info

0

Here is a randomized algorithm that computes a solution: Pairwise[ls_List]:=Module[{tuples, cumulativeNumberOfUniquePairs}, tuples = RandomSample@Tuples[ls]; cumulativeNumberOfUniquePairs = Length /@ FoldList[Union[#1,Subsets[#2,{2}]]&, {}, tuples]; Pick[tuples, Differences[cumulativeNumberOfUniquePairs], _?Positive] ] The algorithm starts ...

2

Update I've suceeded to find some solutions to particular n-lists (n>3) cases and also I have found a ridiculous short algorithm (2 lines of code) which seems to give the optimal n-tuples lists (==> all the possible pairs are present only once) for a large class of configurations where the input n-lists have all the same number of elements.(And I think ...

0

That's a possible solution. I was working exactly on the same problem (nice combination!!!) just last week, but in my case N-tuples have length 6 and not 2 as in your case. However, here I'll post the excerpt of my code for the case of your interest. Just for curiosity: the solution I found has been achieved after many failures. I started thinking about ...

9

More a comment than an answer, (but I have not enough reputation): This is a well known problem, although by far not solved. (One might not expect, but is of very practical relevance in software testing.) You find a lot of interesting stuff (theory and algorithms) by googling "orthogonal array" or - even better - "mixed orthogonal array". Also the book ...

2

This feels quite a bit like an odd mix of systems of distinct representatives and block designs, although this exact problem isn't coming to mind as a particular construction in any of these combinatorial contexts. It would probably help to pull out a book about matroids too -- that's not my forte either. It's important to note that all of your sets will be ...

3

I came up with a little algorithm that produces minimal lists of paths. I might be overlooking something, so please let me know if you find any mistakes. I shall focus on the case where the input list has 3 sublists, which I shall call layers henceforth. Cases with more than three layers can be computed recursively. The algorithm is based on three ...

Top 50 recent answers are included