How to speed up the following algorithm?

Question

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}] // Developer`ToPackedArray;
weights = RandomReal[{0, 1}, Length[pairs]];
weightspairs = Join[Partition[weights, 1], pairs, 2];
Do[
  generatedPairsStep = 
   RandomSample[weightspairs[[All, 1]] -> weightspairs, 1];
  If[i == 1,
   pairssampling = generatedPairsStep,
   pairssampling = Join[pairssampling, generatedPairsStep];
   ];
  nlist = Drop[pairssampling, 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}] // 
    Developer`ToPackedArray; // AbsoluteTiming
weights = RandomReal[{0, 1}, Length[pairs]];
weightspairs = Join[Partition[weights, 1], pairs, 2];
nseed = ntest/2;
Do[
  generatedPairsStep = 
   RandomChoice[weightspairs[[All, 1]] -> weightspairs, nseed] // 
    RandomSample;
  par = {{}};
  nTempList = {};
  Do[If[! MemberQ[nTempList, generatedPairsStep[[m]][[2]]] && ! 
       MemberQ[nTempList, generatedPairsStep[[m]][[3]]],
     par = Join[par, {generatedPairsStep[[m]]}];
     nTempList = Join[nTempList, Drop[generatedPairsStep[[m]], 1]]];
   , {m, 1, nseed, 1}];
  If[i == 1,
   pairssampling = Drop[par, 1],
   pairssampling = Join[pairssampling, Drop[par, 1]];
   ];
  nlist = nTempList;
  weightspairs = 
   compiledsel[weightspairs, nlist] // Developer`ToPackedArray;
  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.

Answer 1

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}] // Developer`ToPackedArray;
 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.}}} *)

Answer 2

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
 ]