possible.rb

 1	 # Class can be used for either Permutations or Combinations.
 2	 # Examples for each are found below.
 3	 #
 4	 # .setParams(ARRAY) -- sets the parameter list
 5	 # .addParam(ITEM ARRAY) -- adds the item to the current list
 6	 # .getCombos({nil|NUMBER}) -- generates combination (number of params 'choose' argument number)
 7	 # .getPerms() -- generates permutations
 8	 #
 9	 # .count -- Total number of generated sets
 10	 # .table -- Array of generated sets (each row is an Array of values)
 11	 # .type -- what was generated (combination | permutation)
 12	 # .params -- Array of parameters (Permutation will be an Array of Arrays)
 13	 # .c_size -- Choose size for combination (defaults to # of params) 
 14	 #
 15	 class Possibility
 16	    attr_reader :count, :table, :type, :params, :c_size
 17	 
 18	    def initialize(params=Array.new)
 19	       @count = 0
 20	       @table = Array.new
 21	       @type = ""
 22	       @params = params
 23	    end
 24	 
 25	    def setParams(params)
 26	       @params.replace(params)
 27	    end
 28	 
 29	    def addParam(param)
 30	       @params.push(param)
 31	    end
 32	 
 33	    def getCombos(size=@params.length)
 34	       @c_size = size
 35	       @type = "combination"
 36	       @table.clear
 37	       combination(@params,Array.new)
 38	       @table.uniq!
 39	       @count = @table.length
 40	       return @count
 41	    end
 42	 
 43	    def getPerms()
 44	       @c_size = 0 #not used
 45	       @type = "permutation"
 46	       @table.clear
 47	       permutation(@params,Array.new)
 48	       @count = @table.length
 49	       return @count
 50	    end
 51	 
 52	 private
 53	 
 54	    #recursive function for combinations
 55	    def combination(params,str)
 56	       if(str.length == @c_size)
 57	          @table.push(str)
 58	       else
 59	          if(params.length == 1)
 60	             @table.push(str.push(params[0]))
 61	          else
 62	             params.each_with_index do |item,i|
 63	                newstr = str.dup.push(item)
 64	                newparams = params.dup
 65	                newparams.slice!(i)
 66	                combination(newparams,newstr)
 67	             end
 68	          end
 69	       end
 70	       return 0
 71	    end
 72	 
 73	    #recursive function for permutations
 74	    def permutation(params,str)
 75	       if(str.length == @params.length)
 76	          @table.push(str)
 77	       else
 78	          params[0].each do |item|
 79	             newstr = str.dup
 80	             newstr.push(item)
 81	             newparams = params.dup
 82	             newparams.slice!(0)
 83	             permutation(newparams,newstr)
 84	          end
 85	       end
 86	       return 0
 87	    end
 88	 end
 89	 
 90	 ##########################################
 91	 # Following produces a "4 choose 3" output
 92	 # (duplicates are always removed)
 93	 #
 94	 #Produces:
 95	 #
 96	 #combination
 97	 #1,1,2,3
 98	 #total: 12
 99	 #1 1 2
 100	 #1 1 3
 101	 #1 2 1
 102	 #1 2 3
 103	 #1 3 1
 104	 #1 3 2
 105	 #2 1 1
 106	 #2 1 3
 107	 #2 3 1
 108	 #3 1 1
 109	 #3 1 2
 110	 #3 2 1
 111	 
 112	 c = Possibility.new( ['1','1','2','3'] )
 113	 c.getCombos(3)
 114	 puts c.type, c.params.join(',')
 115	 puts "total: #{c.count}"
 116	 c.table.each do |combo|
 117	    puts combo.join(' ')
 118	 end
 119	 
 120	 ##########################################
 121	 # Following adds [0,1] as a parameter, 4 times
 122	 # to produce the equivalent of a 4bit number
 123	 #
 124	 #Produces:
 125	 #
 126	 #permutation
 127	 #[0,1][0,1][0,1][0,1]
 128	 #total: 16
 129	 #0 0 0 0
 130	 #0 0 0 1
 131	 #0 0 1 0
 132	 #0 0 1 1
 133	 #0 1 0 0
 134	 #0 1 0 1
 135	 #0 1 1 0
 136	 #0 1 1 1
 137	 #1 0 0 0
 138	 #1 0 0 1
 139	 #1 0 1 0
 140	 #1 0 1 1
 141	 #1 1 0 0
 142	 #1 1 0 1
 143	 #1 1 1 0
 144	 #1 1 1 1
 145	 
 146	 p = Possibility.new()
 147	 4.times { p.addParam([0,1]) }
 148	 p.getPerms()
 149	 puts p.type
 150	 print p.params.map {|param| '['+param.join(',')+']'},"\n"
 151	 puts "total: #{p.count}"
 152	 p.table.each do |perm|
 153	    puts perm.join(' ')
 154	 end