rubycodeenumeratingallnchoosekcombinatio

Generating all the combinations is such a mechanical task but when it comes to writing a program for such a task, usually one is always jolted, because it requires a variable number of for loops. Recursive formula (n,r) = (n-1,r) + (n-1,r-1) can always be used but it is horribly slow. Here is how Ruby shines, the following code generates variable number of for loops on the fly and evaluates it, listing out all the combinations.

def nck(n,k)

str = "n = #{n}\n"

str << "k = #{k}\n"

str << "for i1 in 1..n\n"

for i in 2..k

str << "for i#{i} in i#{i-1}+1..n\n"

end

str << "print \""

for i in 1..k

str << "\#{i#{i}} "

end

str << "\\n\"\n"

for i in 1..k

str << "end\n"

end

print "evaluating\n"

puts str

eval(str)

end

nck(ARGV[0].to_i,ARGV[1].to_i)

# no error checking ... please beware of it

Running the above code at the prompt looks as below ...

$ ruby nck.rb 5 4

evaluating

n = 5

k = 4

for i1 in 1..n

for i2 in i1+1..n

for i3 in i2+1..n

for i4 in i3+1..n

print "#{i1} #{i2} #{i3} #{i4} \n"

end

end

end

end

1 2 3 4

1 2 3 5

1 2 4 5

1 3 4 5

2 3 4 5