Getting all combinations of array items while preserving sequence - Ruby

Question

Given an array of strings

["the" "cat" "sat" "on" "the" "mat"]

I'm looking to get all combinations of items in sequence, from any starting position, e.g.

["the"]
["the" "cat"]
["the" "cat" "sat"]
...
["cat" "sat" "on" "the" "mat"]
["sat" "on" "the" "mat"]
["on" "the" "mat"]
...
["sat" "on"]
["sat" "on" "the"]

Combinations out of the original sequence or with missing elements are disallowed, e.g.

["sat" "mat"] # missing "on"
["the" "on"]  # reverse order

I'd also like to know if this operation has a particular name or if there's a neater way of describing it.

Thanks.

Mladen Jablanović · Accepted Answer · 2010-08-11 11:21:46Z

6

If you're into one-liners, you might try

(0..arr.length).to_a.combination(2).map{|i,j| arr[i...j]}

BTW, I think those are called "all subsequences" of an array.

answered Aug 11, 2010 at 11:21

Mladen Jablanović

44.2k13 gold badges92 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jörg W Mittag Over a year ago

He's asking about substrings, not subsequences. Every substring is also a subsequence, but not all subsequences are substrings. For example, 235 is a subsequence of 123456 but not a substring.

Mladen Jablanović Over a year ago

Thanks, I didn't know about the difference. So, substrings need to be consecutive elements in the original array, while subsequences don't.

butterywombat Over a year ago

In any case the above is finding the substrings, not subsequences so, just semantics...elegant solution :)

Marc-André Lafortune · Accepted Answer · 2010-08-11 14:31:08Z

4

Just iterate over each starting position and for each starting position over each possible end position:

arr = ["the", "cat", "sat", "on", "the", "mat"]
(0 ... arr.length).map do |i|
  (i ... arr.length).map do |j|
    arr[i..j]
  end
end.flatten(1)
#=> [["the"], ["the", "cat"], ["the", "cat", "sat"], ["the", "cat", "sat", "on"], ["the", "cat", "sat", "on", "the"], ["the", "cat", "sat", "on", "the", "mat"], ["cat"], ["cat", "sat"], ["cat", "sat", "on"], ["cat", "sat", "on", "the"], ["cat", "sat", "on", "the", "mat"], ["sat"], ["sat", "on"], ["sat", "on", "the"], ["sat", "on", "the", "mat"], ["on"], ["on", "the"], ["on", "the", "mat"], ["the"], ["the", "mat"], ["mat"]]

Requires ruby 1.8.7+ (or backports) for flatten(1).

edited Aug 11, 2010 at 14:31

Marc-André Lafortune

79.8k17 gold badges172 silver badges167 bronze badges

answered Aug 11, 2010 at 10:33

sepp2k

372k56 gold badges687 silver badges687 bronze badges

1 Comment

Marc-André Lafortune Over a year ago

I took the liberty of editing the ranges to use ... instead of -1. Also note that Ruby 1.9.2 introduces flat_map which is basically equivalent to map{}.flatten(1). Also available with backports :-)

Jaykumar Patel · Accepted Answer · 2014-04-03 09:06:07Z

0

here you can get all the combinations

(1...arr.length).map{ | i | arr.combination( i ).to_a }.flatten(1)

edited Apr 3, 2014 at 9:06

Jaykumar Patel

27.7k12 gold badges79 silver badges76 bronze badges

answered Apr 3, 2014 at 8:28

rajagopal

494 bronze badges

Collectives™ on Stack Overflow

Getting all combinations of array items while preserving sequence - Ruby

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related