########################################################################
##
## Copyright (C) 2001-2021 The Octave Project Developers
##
## See the file COPYRIGHT.md in the top-level directory of this
## distribution or <https://octave.org/copyright/>.
##
## This file is part of Octave.
##
## Octave is free software: you can redistribute it and/or modify it
## under the terms of the GNU General Public License as published by
## the Free Software Foundation, either version 3 of the License, or
## (at your option) any later version.
##
## Octave is distributed in the hope that it will be useful, but
## WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with Octave; see the file COPYING.  If not, see
## <https://www.gnu.org/licenses/>.
##
########################################################################

## -*- texinfo -*-
## @deftypefn {} {} uniqueperms (@var{v})
## Generate all unique permutations of vector @var{v} with one row per
## permutation.
##
## The result has size @code{N * @var{n}}, where @var{n} is the length of
## @var{v} and N is the number of unique permutations.
## No repetitions are included in the output.
##
## Example
##
## @example
## @group
## uniqueperms ([1, 1, 2])
## @result{}
##   2   1   1
##   1   2   1
##   1   1   2
## @end group
## @end example
##
## Programming Notes:
##
## 1. It is much less memory intensive to call uniqueperms(...) than to call
## unique(perms(...), "rows"), particularly for many repeated elements.
## Try uniqueperms([1 1 1 1 2 2 2 2 3 3 3 3]) for example.
##
## 2. It is usually much slower to call uniqueperms(...) than it is to call
## unique(perms(...),"rows"), trading away speed to reduce the memory footprint.
##
## 3. The results are not guaranteed to be in any particular order.
##
## @seealso{permute, randperm, nchoosek, perms}
## @end deftypefn

function retval = uniqueperms (v)
  if (isempty(v))
    retval = [];
    return;
  endif

  n = length (v);
  uniquevec = unique (v);
  numunique = length (uniquevec);
  if (numunique == 1) # simple special case
    retval = v(:)';
    return;
  elseif (numunique == n) # fall back to perms if all elements different
    retval = perms (v);
    return;
  end

  # general case
  retval = [];
  for i = uniquevec
    # for each unique element, we remove it, permute the rest of the vector
    # and put the removed element back at the end, recursing where needed.
    v2 = v;
    v2(find(v2==i,1)) = [];
    tmp = uniqueperms (v2);
    tmp(:,end+1) = i;
    retval = [retval; tmp];
  endfor
endfunction
