# How to speed up the following algorithm?

I have some random combinations of numbers pairs (where numbers range from 1 to some ntest) and weights to them weights, merged into weightspairs. I need to generate n/2 fully distinct pairs (such that each number is repeated in the generated set only once) using RandomSample/RandomChoice.

I do this iteratively: generate the random combination, remove all occurrences of the numbers from the random combination from weightspairs, and repeat:

ntest = 100;
pairs = Subsets[Range[ntest] // N, {2}] // DeveloperToPackedArray;
weights = RandomReal[{0, 1}, Length[pairs]];
weightspairs = Join[Partition[weights, 1], pairs, 2];
Do[
RandomSample[weightspairs[[All, 1]] -> weightspairs, 1];
If[i == 1,
];
nlist = Flatten[pairssampling[[All, {2, 3}]]] // Sort;
matchesNList[row_] :=
MemberQ[nlist, row[[2]]] || MemberQ[nlist, row[[3]]];
weightspairs = DeleteCases[weightspairs, _?matchesNList];
If[Length[weightspairs] == 0, Break[]]
, {i, 1, ntest/2, 1}] // AbsoluteTiming


The method is slow, taking around ~1 second, and I need to consider a much larger ntest. It is clear that some part of the code may be compiled, but the problem is that the approach itself is not optimal, especially in the part DeleteCases.

Could you please tell me how to speed it up?

Edit

The following code works much faster, although it is still algorithmically poor (the time scales as ntest^3):

compiledsel =
Compile[{{data, _Real, 2}, {nlist, _Real, 1}},
Select[data, ! MemberQ[nlist, #[[2]]] && !
MemberQ[nlist, #[[3]]] &], CompilationTarget -> "C",
RuntimeOptions -> "Speed", RuntimeAttributes -> {Listable},
Parallelization -> True];
ntest = 400;
pairs = Subsets[Range[ntest] // N, {2}] //
DeveloperToPackedArray; // AbsoluteTiming
weights = RandomReal[{0, 1}, Length[pairs]];
weightspairs = Join[Partition[weights, 1], pairs, 2];
nseed = ntest/2;
Do[
RandomChoice[weightspairs[[All, 1]] -> weightspairs, nseed] //
RandomSample;
par = {{}};
nTempList = {};
, {m, 1, nseed, 1}];
If[i == 1,
];
nlist = nTempList;
weightspairs =
compiledsel[weightspairs, nlist] // DeveloperToPackedArray;
If[Length[weightspairs] == 0, Break[]]
, {i, 1, ntest/2, 1}] // AbsoluteTiming


Here, however, I sample the pairs not one-by-one, but a much larger amount of times.

• You don't need the // N on the second line - they're just integers. Commented Mar 11 at 14:05
• Given your other recent questions. It sounds like you just want to do something like this. Though this minimizes weight instead of maximizes it, you could invert your weights: g = Graph[UndirectedEdge @@@ pairs, EdgeWeight -> weights]; FindEdgeCover[g] Commented Mar 11 at 14:08
• @flinty : if not converting to N, the matrix would not be a packed array, whixh slows down the calculations. Commented Mar 11 at 15:12
• Is this different from what I commented on in one of several similar prior posts? Commented Mar 11 at 15:51
• @DanielLichtblau : yes, the weight may be generic, and in particular it kay be some non-trivial product of the quantities belonging to the pair. Commented Mar 11 at 16:14

If the weights are based on pairs rather than separably based on individual elements, you can take a random sample of the full set of pairs by weights and sequentially remove each that has an element already used. This save the time of sequential removals interleaved with selections.

AbsoluteTiming[
ntest = 100;
pairs = Subsets[Range[ntest] // N, {2}] // DeveloperToPackedArray;
weights = RandomReal[{0, 1}, Length[pairs]];
weightspairs = Join[Partition[weights, 1], pairs, 2];
generated = RandomSample[weightspairs[[All, 1]] -> weightspairs];
reduced =
Map[If[TrueQ[seen[#[[2]]]] || TrueQ[seen[#[[3]]]],
Nothing, (Map[(seen[#] = True) &, Rest@#]; #)] &, generated];
ClearAll[seen];
reduced]

(* Out[291]= {0.010269, {{0.938872, 26., 75.}, {0.526988, 7.,
95.}, {0.828101, 6., 45.}, {0.534685, 31., 94.}, {0.117848, 8.,
15.}, {0.507512, 61., 71.}, {0.458398, 37., 80.}, {0.998765, 3.,
38.}, {0.92762, 16., 85.}, {0.515526, 18., 52.}, {0.194932, 23.,
86.}, {0.600985, 1., 97.}, {0.964535, 24., 50.}, {0.870533, 27.,
83.}, {0.56242, 22., 40.}, {0.842291, 13., 46.}, {0.718279, 19.,
25.}, {0.401877, 76., 93.}, {0.933245, 34., 87.}, {0.0881186, 2.,
30.}, {0.614855, 4., 63.}, {0.721995, 11., 33.}, {0.339263, 69.,
77.}, {0.655064, 21., 73.}, {0.502061, 57., 66.}, {0.969345, 60.,
100.}, {0.0779854, 29., 55.}, {0.639042, 9., 62.}, {0.784737, 41.,
70.}, {0.458987, 17., 68.}, {0.662033, 10., 48.}, {0.766491, 47.,
49.}, {0.940952, 51., 53.}, {0.638249, 79., 91.}, {0.662277, 42.,
74.}, {0.319627, 72., 90.}, {0.580323, 12., 78.}, {0.682557, 5.,
56.}, {0.432495, 67., 81.}, {0.829214, 36., 43.}, {0.73324, 20.,
82.}, {0.961731, 28., 32.}, {0.254803, 44., 54.}, {0.575702, 58.,
88.}, {0.297704, 14., 64.}, {0.874084, 84., 98.}, {0.507488, 39.,
65.}, {0.425491, 89., 96.}, {0.927165, 59., 99.}, {0.563442, 35.,
92.}}} *)

• Thanks! Your approach works somewhat faster than my revised approach (in the edit of the question). In particular, it seems to have a better scaling of time with ntest. Commented Mar 11 at 23:45
• It should be roughly quadratic in ntest. Commented Mar 11 at 23:57

Random as in "each result should be equally likely"? Then you could sample a random subset of length 2 n with RandomSample and then apply an RandomPermutation. Afterwards, apply Partition[#,2]&:

Partition[
Part[
RandomSample[Range[1, ntest], 2 n],
PermutationList[RandomPermutation[n], n]
],
2
]