CoCoA » CoCoA-5

I wanted a RandomSubset function which generated a random subset of 1..n of cardinality r. I was surprised when CoCoA reported that I could not define the fn as the name was already a package exported variable.

I have a slight preference for my fn over the existing one which generated a random subset of a set represented as a list. The fns are closely related:

RandomSubset(L,r) == [L[i] | i in RandomSubsetJAA(len(L),r)];
RandomSubsetJAA(n,r) == RandomSubset(1..n, r) 

Why do I prefer my fn? It somehow "feels simpler", and might be slightly easier to implement efficiently in C++; the current defn requires copying some/all elements of the input list L which could be expensive if the elements are large.

For completeness here is my defn (taken from Wikipedia "Reservoir sorting"?)

define RandomSubset(n,r)
  subset := 1..r;
  for k := r+1 to n do
    i := random(1,k);
    if i > r then continue; endif;
    subset[i] := k;
  endfor;
  return sorted(subset);
enddefine; -- RandomSubset

We could simply have both; that way the user can choose which is more convenient (or efficient).

If we do choose to have both, should they have the same name or different names?

Maybe my fn should be called RandomIndexSubset? (long and a rather ugly)

I suggest having also RandomTuple(n,r) which is indeed pretty simple: in CoCoA

define RandomTuple(L, r)
  return [ L[random(1,len(L))] | i in 1..r ];
enddefine; -- RandomSubset

I added to NotBuiltin.cpkg the functions

Export RandomSubset;
Export RandomSubsetIndices;
Export RandomTuple;
Export RandomTupleIndices;

documentation done (and cvs'ed)

When we implement the "Indices" in CoCoALib we'll remove them from "NotBuiltin".
(Remember: shift indices by 1)

I have added defns to CoCoALib of RandomSubsetIndices and RandomTupleIndices. These names are very long :-/

Not entirely convinced by the usefulness of RandomTupleIndices.

Also added defns to BuiltinFunctions.C

Not yet: doc, examples, tests.

Where should the new functions go?

Currently they are in a new file combinatorics.C because I could not see any other good place tro put them. Is this OK?

John Abbott wrote:

Where should the new functions go?

Currently they are in a new file combinatorics.C because I could not see any other good place tro put them. Is this OK?

yes

Checked in.
You'll have to remove interrupt.C from src/AlgebraicCore/Makefile until I can check those files in... hot choc break now! :-)

John Abbott wrote:

I have added defns to CoCoALib of RandomSubsetIndices and RandomTupleIndices. These names are very long :-/

Not entirely convinced by the usefulness of RandomTupleIndices.

Nor am I, for cocoalib. But I know someone who should make good use of RandomTuple in cocoa-5 ;-)

Also added defns to BuiltinFunctions.C

cvs?

Not yet: doc, examples, tests.

I can do that.

I have checked in RandomSubsetIndices and RandomTupleIndices (in CoCoALib); also the interface fns in BuiltinFunctions.C.

I have not implemented RandomSubset in C++; nor RandomTuple.