diff options
| -rw-r--r-- | eval.c | 2 | ||||
| -rw-r--r-- | lib.c | 32 | ||||
| -rw-r--r-- | lib.h | 2 | ||||
| -rw-r--r-- | txr.1 | 65 |
4 files changed, 90 insertions, 11 deletions
@@ -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)); @@ -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); @@ -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); @@ -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 @@ -39030,18 +39032,65 @@ function. The 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 ]) |