[patch] shuf.c: Permutation With Replacement

[Alexander Horn]

Add support for permutations with replacement:

For example:

shuf <<EOF
clubs
hearts
diamonds
spades
EOF

might output:

clubs
diamonds
spades
diamonds

Please let me know if you would like me to make any changes to the patch.


CHANGELOG
=========

shuf.c:
 Add "-w", "--with-replacement" switches
randperm.h:
 Add "with_replacement" integer parameter to randperm_new().
randperm.c:
 Add functionality to generate a permutation with replacement.
coreutils.texi:
 Add "-w", "--with-replacement" description.

--
Alexander Horn
http://www2.truman.edu/~ah428

===========================diff:begin================================


Index: doc/coreutils.texi
===================================================================
RCS file: /sources/coreutils/coreutils/doc/coreutils.texi,v
retrieving revision 1.370
diff -u -r1.370 coreutils.texi
--- doc/coreutils.texi  19 Feb 2007 21:11:36 -0000      1.370
+++ doc/coreutils.texi  20 Feb 2007 20:51:33 -0000
@@ -4045,6 +4045,33 @@
Use @var{file} as a source of random data used to determine which
permutation to generate.  @xref{Random sources}.

address@hidden -w
address@hidden --with-replacement
address@hidden -w
address@hidden --with-replacement
address@hidden permutation with replacement
+Output permutation with replacement.
+
address@hidden
+shuf <<EOF
+clubs
+hearts
+diamonds
+spades
+EOF
+
address@hidden example
+
address@hidden
+might output:
+
address@hidden
+clubs
+diamonds
+spades
+diamonds
address@hidden example
+
@item -z
@itemx --zero-terminated
@opindex -z
Index: lib/randperm.c
===================================================================
RCS file: /sources/coreutils/coreutils/lib/randperm.c,v
retrieving revision 1.2
diff -u -r1.2 randperm.c
--- lib/randperm.c      26 Aug 2006 06:55:58 -0000      1.2
+++ lib/randperm.c      20 Feb 2007 20:51:33 -0000
@@ -63,7 +63,7 @@
   is zero.  */

size_t *
-randperm_new (struct randint_source *r, size_t h, size_t n)
+randperm_new (struct randint_source *r, size_t h, size_t n, int
with_replacement)
{
  size_t *v;

@@ -88,10 +88,18 @@

       for (i = 0; i < h; i++)
         {
-           size_t j = i + randint_choose (r, n - i);
-           size_t t = v[i];
-           v[i] = v[j];
-           v[j] = t;
+                       if(with_replacement)
+        {
+          size_t j = randint_choose (r, n);
+               v[i] = j;
+        }
+      else
+                         {
+          size_t j = i + randint_choose (r, n - i);
+               size_t t = v[i];
+               v[i] = v[j];
+               v[j] = t;
+                   }
         }

       v = xnrealloc (v, h, sizeof *v);
Index: lib/randperm.h
===================================================================
RCS file: /sources/coreutils/coreutils/lib/randperm.h,v
retrieving revision 1.1
diff -u -r1.1 randperm.h
--- lib/randperm.h      8 Aug 2006 22:22:47 -0000       1.1
+++ lib/randperm.h      20 Feb 2007 20:51:33 -0000
@@ -1,4 +1,4 @@
#include "randint.h"
#include <stddef.h>
size_t randperm_bound (size_t, size_t);
-size_t *randperm_new (struct randint_source *, size_t, size_t);
+size_t *randperm_new (struct randint_source *, size_t, size_t, int
with_replacement);
Index: src/shuf.c
===================================================================
RCS file: /sources/coreutils/coreutils/src/shuf.c,v
retrieving revision 1.4
diff -u -r1.4 shuf.c
--- src/shuf.c  29 Sep 2006 16:52:48 -0000      1.4
+++ src/shuf.c  20 Feb 2007 20:51:33 -0000
@@ -95,6 +95,7 @@
  {"head-count", required_argument, NULL, 'n'},
  {"output", required_argument, NULL, 'o'},
  {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
+  {"with-replacement", no_argument, NULL, 'w'},
  {"zero-terminated", no_argument, NULL, 'z'},
  {GETOPT_HELP_OPTION_DECL},
  {GETOPT_VERSION_OPTION_DECL},
@@ -245,6 +246,7 @@
main (int argc, char **argv)
{
  bool echo = false;
+       bool with_replacement = false;
  size_t lo_input = SIZE_MAX;
  size_t hi_input = 0;
  size_t head_lines = SIZE_MAX;
@@ -268,7 +270,7 @@

  atexit (close_stdout);

-  while ((optc = getopt_long (argc, argv, "ei:n:o:z", long_opts, NULL)) != -1)
+  while ((optc = getopt_long (argc, argv, "ei:n:o:wz", long_opts, NULL)) != -1)
    switch (optc)
      {
      case 'e':
@@ -333,6 +335,10 @@
       random_source = optarg;
       break;

+      case 'w':
+       with_replacement = true;
+       break;
+
      case 'z':
       eolbyte = '\0';
       break;
@@ -401,7 +407,7 @@
      && (ferror (stdin) || fclose (stdin) != 0))
    error (EXIT_FAILURE, errno, _("read error"));

-  permutation = randperm_new (randint_source, head_lines, n_lines);
+  permutation = randperm_new (randint_source, head_lines, n_lines,
with_replacement);

  if (outfile && ! freopen (outfile, "w", stdout))
    error (EXIT_FAILURE, errno, "%s", quotearg_colon (outfile));


===========================diff:end================================