Say you have the set 1,2,3,4,5,6 and you want to know all combinations, not permutations, of the set. Here is a Ruby script to do so.
elements=[1,2,3,4,5,6]
t1=Time.now
combinations=[]
elements.each_with_index do |element,i|
# the by-itself combination
combinations<<[element]
# the last item's combinations are already defined
unless i==elements.size-1
elements[(i+1)..(elements.size-1)].each do |next_element|
combinations<<(combinations.last.dup<<next_element)
end
end
end
t2=Time.now
combinations.each {|c|puts c.join(',')}
puts "it took #{(t2-t1)*1000}ms to generate this set"
and the output:
1 1,2 1,2,3 1,2,3,4 1,2,3,4,5 1,2,3,4,5,6 2 2,3 2,3,4 2,3,4,5 2,3,4,5,6 3 3,4 3,4,5 3,4,5,6 4 4,5 4,5,6 5 5,6 6 it took 8ms to generate this set
It also works with words. The real-world case for this is that I’m working on a keyword co-occurrence database. I want to know, out of a given set of survey responses, the frequency of words which appear in the same sentence. For the given sentence I love Ruby, it is such a great programming language — and powerful, too., with the common words removed…
elements=["love","Ruby","great","programming","language","powerful"]
and the output:
love love,Ruby love,Ruby,great love,Ruby,great,programming love,Ruby,great,programming,language love,Ruby,great,programming,language,powerful Ruby Ruby,great Ruby,great,programming Ruby,great,programming,language Ruby,great,programming,language,powerful great great,programming great,programming,language great,programming,language,powerful programming programming,language programming,language,powerful language language,powerful powerful it took 13ms to generate this set
This script doesn’t handle large sets!
elements=(1..500).to_a it took 30819ms to generate this set elements=(1..5000).to_a #my computer crashed from lack of memory!
But if you can reduce the depth of combinations…
There isn’t much value (at least in the context of what I am doing!) in indexing every possible combination of words in a large text. Really, I only need maybe four-word combinations. This script will work with a large text because the result set is relatively small because it limits the combination depth to three elements.
max=3
elements=[1,2,3,4,5,6]
t1=Time.now
combinations=[]
elements.each_with_index do |element,i|
# the by-itself combination
combinations<<[element]
# the last item's combinations are already defined
unless i==elements.size-1
elements[(i+1)..(elements.size-1)].each do |next_element|
c=combinations.last.dup<<next_element
c.delete_at(1) until c.size<=max
combinations<<c
end
end
end
t2=Time.now
combinations.each {|c|puts c.join(',')}
puts "it took #{t2-t1}ms to generate this set"
1 1,2 1,2,3 1,3,4 1,4,5 1,5,6 2 2,3 2,3,4 2,4,5 2,5,6 3 3,4 3,4,5 3,5,6 4 4,5 4,5,6 5 5,6 6 it took 13ms to generate this set
Now I can work with large texts!
elements=(1..5000).to_a it took 28370ms to generate this set
Now I have what I need to build a database index representing combinations of words in sentences. From there, I can find all sentences with, say, powerful and language in them (because all sentences will be indexed according to the combinations of words that appear in them). However, knowing to look for powerful and language in advance is not my goal -- I want the database to tell me the most frequent co-occurrences, so that I can examine them. My goal is to have the database tell me, in essence, the most common combination of words the combination of problem and feature so that I can pinpoint what people are talking about without having to read every single sentence. (I'm pretty sure this is impossible since people might not use the same terminology even though they're all talking about the same thing).
But more on this topic later...