From 77deceded0e5c9143e01d07a19eb219b3273151b Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 1 Jul 2024 18:10:49 -0700 Subject: New functions: cshuffle and cnshuffle. These functions find random cyclic permutations. * eval.c (eval_init): Register cshuffle and cnshuffle intrinsics. * lib.c (nshuffle_impl): New static function, formed out of nshuffle. (nhuffle): Now wrapper around nshuffle_impl. (shuffle): Also wraps nshuffle_impl rather than nshuffle. (cnshuffle, cshuffle): New funtions. * lib.h (cnshuffle, cshuffle): Declared. * txr.1: Documented new functions. Also added warning about limitations on permutation reachability in relation to PRNG state size. --- eval.c | 2 ++ lib.c | 32 ++++++++++++++++++++++++++------ lib.h | 2 ++ txr.1 | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- 4 files changed, 90 insertions(+), 11 deletions(-) diff --git a/eval.c b/eval.c index 2fd252e1..478b1345 100644 --- a/eval.c +++ b/eval.c @@ -7787,6 +7787,8 @@ void eval_init(void) reg_fun(intern(lit("ssort"), user_package), func_n3o(ssort, 1)); reg_fun(intern(lit("nshuffle"), user_package), func_n2o(nshuffle, 1)); reg_fun(intern(lit("shuffle"), user_package), func_n2o(shuffle, 1)); + reg_fun(intern(lit("cnshuffle"), user_package), func_n2o(cnshuffle, 1)); + reg_fun(intern(lit("cshuffle"), user_package), func_n2o(cshuffle, 1)); reg_fun(intern(lit("find"), user_package), func_n4o(find, 2)); reg_fun(intern(lit("rfind"), user_package), func_n4o(rfind, 2)); reg_fun(intern(lit("find-if"), user_package), func_n3o(find_if, 2)); diff --git a/lib.c b/lib.c index 445fa6b8..c00e6401 100644 --- a/lib.c +++ b/lib.c @@ -11664,7 +11664,7 @@ val ssort(val seq, val lessfun, val keyfun) abort(); } -val nshuffle(val seq, val randstate) +static val nshuffle_impl(val seq, val randstate, int cyclic, val self) { seq_info_t si = seq_info(seq); @@ -11674,7 +11674,7 @@ val nshuffle(val seq, val randstate) case SEQ_LISTLIKE: if (cdr(seq)) { - val v = nshuffle(vec_list(seq), randstate); + val v = nshuffle_impl(vec_list(seq), randstate, cyclic, self); val i, l; for (l = seq, i = zero; l; i = succ(i), l = cdr(l)) @@ -11692,7 +11692,7 @@ val nshuffle(val seq, val randstate) return seq; for (i = pred(n); ge(i, one); i = pred(i)) { - val j = random(rs, succ(i)); + val j = random(rs, if3(cyclic, i, succ(i))); val t = ref(seq, i); refset(seq, i, ref(seq, j)); refset(seq, j, t); @@ -11702,19 +11702,39 @@ val nshuffle(val seq, val randstate) } case SEQ_NOTSEQ: case SEQ_TREELIKE: - unsup_obj(lit("nshuffle"), seq); + unsup_obj(self, seq); } abort(); } +val nshuffle(val seq, val randstate) +{ + return nshuffle_impl(seq, randstate, 0, lit("nshuffle")); +} + val shuffle(val seq, val randstate) { + val self = lit("shuffle"); + if (seqp(seq)) + return nshuffle_impl(copy(seq), randstate, 0, self); + type_mismatch(lit("~a: ~s is not a sequence"), self, seq, nao); +} + +val cnshuffle(val seq, val randstate) +{ + return nshuffle_impl(seq, randstate, 1, lit("cnshuffle")); +} + +val cshuffle(val seq, val randstate) +{ + val self = lit("cshuffle"); if (seqp(seq)) - return nshuffle(copy(seq), randstate); - type_mismatch(lit("nshuffle: ~s is not a sequence"), seq, nao); + return nshuffle_impl(copy(seq), randstate, 1, self); + type_mismatch(lit("~a: ~s is not a sequence"), self, seq, nao); } + static val multi_sort_less(val funcs_cons, val llist, val rlist) { cons_bind (funcs, key_funcs, funcs_cons); diff --git a/lib.h b/lib.h index 0c300e8a..f83d59b0 100644 --- a/lib.h +++ b/lib.h @@ -1384,6 +1384,8 @@ val snsort(val seq, val lessfun, val keyfun); val ssort(val seq, val lessfun, val keyfun); val nshuffle(val seq, val randstate); val shuffle(val seq, val randstate); +val cnshuffle(val seq, val randstate); +val cshuffle(val seq, val randstate); val multi_sort(val lists, val funcs, val key_funcs); val sort_group(val seq, val keyfun, val lessfun); val unique(val seq, val keyfun, varg hashv_args); diff --git a/txr.1 b/txr.1 index d5ea3cc6..53d3377b 100644 --- a/txr.1 +++ b/txr.1 @@ -39005,10 +39005,12 @@ in the APL language. [grade "Hello" >] -> (4 2 3 1 0) .brev -.coNP Functions @ shuffle and @ nshuffle +.coNP Functions @, shuffle @, nshuffle @ cshuffle and @ cnshuffle .synb .mets (shuffle < sequence <> [ random-state ]) .mets (nshuffle < sequence <> [ random-state ]) +.mets (cshuffle < sequence <> [ random-state ]) +.mets (cnshuffle < sequence <> [ random-state ]) .syne .desc The @@ -39029,19 +39031,66 @@ function. The .meta random-state argument, if present, is passed to that function. +The +.code cnshuffle +function also pseudorandomly rearranges the elements of +.metn sequence . +It differs from +.code nshuffle +in that it produces a cyclic permutation: a permutation +consisting of a single cycle. + +Whereas +.code nshuffle +may possibly map some, or even all elements to their original locations, +.code cnshuffle +maps every element to a new location (if +.meta sequence +has at least two elements. + +An example of a cyclic permutation is the mapping of +.code "(1 2 3 4)" +to +.codn "(3 1 4 2)" . +The cycle consists of 1 mapping to 3, +3 mapping to 4, 4 mapping to 2, and 2 mapping back to 1. +An example of a permutation which is not cyclic is +.code "(1 2 3 4)" +to +.code "(1 3 4 2)" +which contains two cycles: +.code "(1)" +maps to +.code "(1)" +and +.code "(2 3 4)" +maps to +.codn "(3 4 2)" . +The +.code cnshuffle +function will not produce this permutation; the +.code nshuffle +function may. + The .code nshuffle -function supports hash tables in a manner analogous to the way +and +.code cnshuffle +functions support hash tables in a manner analogous to the way .code nsort supports hash tables; the same remarks apply as in the description of that function. The .code shuffle -function has the same argument requirements and -semantics, but differs from +and +.code cshuffle +functions have the same argument requirements and +semantics as .code nshuffle -in that it avoids in-place modification of +and +.code cnshuffle +respectively, but differ in that it they in-place modification of .metn sequence : a new, shuffled sequence is returned, as if a copy of .meta sequence @@ -39056,6 +39105,12 @@ was introduced in \*(TX 238. Prior to that version, behaved like .codn nshuffle . +Note: The pseudo-random number generator in \*(TX has only 512 bits of state, +which is sufficient for generating the all the permutations of sequences of at +most 98 elements, and the cyclic permutations of sequences of at most 99 +elements. These figures should not be interpreted as guarantees, but as +theoretical maxima. + .coNP Functions @ rot and @ nrot .synb .mets (rot < sequence <> [ displacement ]) -- cgit v1.2.3