OpenEuphoria

1. permcomb.e combinations & permutations

• Posted by ne1uno Nov 30, 2009
• 1037 views

inside the boggle.zip from ck's word challange is permcomb.e to produce combinations and permutations. something like this could easily find a place in the stdlib.

I think I fixed a bug or two for longer permutations and combinations. the word challange was only using 3 and 4 if I recall.

 
-fixed 
--** 
-- the number of selections of r things from n different things 
--  {{{= n! / ( (n-r)! * r! )}}} 
public function nCr(atom n, atom r) 
  if n - r <= 0 then 
      return 1 
  elsif n - r < 1 then 
      return factorial[n] 
  end if 
  return factorial[n] / ( factorial[n-r] * factorial[r]) 
end function 
 
-added 
--** 
-- the number of permutations of r things from n things 
--  {{{= n! / (n-r)!}}} 
public function nPr(atom n, atom r) 
  if n - r < 1 then 
      return factorial[n] 
  end if 
  return factorial[n] - factorial[n-r] 
end function 
 
 
include std/sequence.e 
 
--** 
-- added as a convenience 
-- return all the permutations of all the select combinations 
-- of r elements from s,  make tosort TRUE to return only sorted and unique 
-- 
-- r defaults to length of s 
-- 
-- caution: for more than 4 characters this can be a very large sequence 
-- there probably is loss of efficiency calling for the nth permutation 
--instead of looping inline directly, that may happen in a future version. 
 
public function permcombs(sequence s, integer r=0, integer tosort=1) 
  sequence results={}, t 
   if r <= 0 then r = length(s) end if 
 
    for j = 1 to nCr(length(s), r) do 
          t = select_qrs(j, r, s) 
    for k = 1 to nPr(length(t), r) do --1..length(t) not enough 
        results &= {perm_qs(k, t)} 
    end for 
  end for 
 
  if tosort then 
    return remove_dups(results, RD_SORT) 
  end if 
   
  return results 
end function 
 
 
--also renamed perm_rs to perm_qs 
 
 

any combination/permutation math wiz want to comment? there should be an option for allowing repetitions or preventing them, beyond running unique on the output.

the permutations and combinations agree with output from gsl now.

get the rest of permcomb.e from boggle.zip http://www.usingeuphoria.com