Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 134 ยท Collections

Array Algorithms

Learn Ruby array algorithms - combination, permutation, product, each_slice, each_cons, transpose, rotate, zip, and seeded shuffle and sample - with runnable examples.

Once you know how to loop over an array with each and map (see Iterating and Transforming Arrays), a second layer of methods opens up: ones that build new arrangements of your data. Every pair of toppings on a pizza. Every ordering of three tasks. A list cut into pages of ten. A table flipped so rows become columns. In many languages you would write nested loops for each of these. In Ruby, each one is a single method call.

This lesson walks through the arrangement methods in the core library: combination, permutation, product, each_slice, each_cons, transpose, rotate, zip, cycle, and the random pair shuffle and sample. You will also see how fast the number of results grows, because that growth is the one thing that can quietly ruin a program.

Combinations: choose some, order does not matter

A combination is a group picked from a collection where the order inside the group is irrelevant. [ham, olive] and [olive, ham] are the same pizza. combination(n) yields every group of n elements.

Ruby Choosing pairs and triples

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Called without a block, combination returns an enumerator, a lazy object that produces results on demand (see Enumerators). Calling to_a on it collects everything, while count, first(3) or find can stop early. Two edge cases are worth remembering from the last two lines of output: choosing zero elements gives exactly one combination (the empty group), and choosing more elements than exist gives none.

Permutations: order matters

A permutation counts [a, b] and [b, a] as different results. This is what you want for ordering tasks, ranking runners or building anagrams. Without an argument, permutation uses every element; with an argument it picks that many.

Ruby Orderings of a small list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Three tasks have six orderings (3 x 2 x 1), but only three pairs when order is ignored. The difference between the two methods is a factor of n! for groups of size n, which is why you should always ask yourself first: does order matter?

Results grow explosively. Ten items have 3,628,800 permutations; twenty have more than two quintillion. A TryIt that calls (1..20).to_a.permutation.to_a would run out of memory long before it finished. Prefer the lazy form (permutation.first(5), permutation.lazy.select { ... }.first) or find a smarter algorithm when the input is not tiny. Use count on the enumerator only for small inputs, since it still walks every result.

There are two siblings: repeated_combination(n) and repeated_permutation(n) allow the same element to be chosen more than once, like rolling a die several times.

product: every pairing of several lists

product is the Cartesian product: it pairs every element of the receiver with every element of each argument.

Ruby Menus and grids with product

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The result is an array of arrays, with the first list varying slowest. With more than two lists the size is the product of all sizes (3 x 2 x 2 = 12 above). It is a clean replacement for nested loops, and it combines nicely with select when you want only the pairs that satisfy a rule.

Cutting a list into pieces: each_slice and each_cons

Two methods from Enumerable walk through an array in chunks:

  • each_slice(n) cuts it into non-overlapping pieces of n (the last one may be shorter).
  • each_cons(n) slides a window of n across it, overlapping by n - 1.
Ruby Pages and sliding windows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Use each_slice for pagination, batching database inserts and splitting work between workers. Use each_cons whenever you compare neighbours: differences, moving averages, "is the list sorted", "does a word contain this three-letter run". Both return enumerators without a block, so map, count and first chain on directly.

Flipping a table: transpose

An array of equal-length rows is a table. transpose swaps rows and columns.

Ruby Rows become columns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

After transposing, every inner array holds one subject across all students, so column statistics become one-liners. Transposing twice gives back the original table. The rows must have the same length. What happens when they do not?

Ruby Ragged rows (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Ruby raises an IndexError whose message is element size differs (2 should be 3). The fix is to make the rows even first, for example by padding: rows.map { |r| r + [nil] * (width - r.size) }.

zip, rotate and cycle

zip interleaves arrays position by position. It is the lightweight cousin of transpose for two or three lists, and it pairs naturally with to_h.

rotate(n) moves the first n elements to the end (a negative n goes the other way). It does not change the receiver, while rotate! does. cycle repeats an array forever, so always pair it with something that stops, like first(5) or a break.

Ruby zip, rotate and cycle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

When the arguments are shorter than the receiver, zip pads with nil. When they are longer, the extra elements are dropped, as the last example shows. Calling shifts.next on the infinite cycle enumerator hands out one value at a time and wraps around forever.

Random order, repeatable results: shuffle and sample

shuffle returns a new array in random order and sample picks one (or several) random elements. Real randomness makes output differ on every run, which is bad for tests and for lessons. Pass your own Random object with a seed and the sequence becomes repeatable.

Ruby Seeded shuffle and sample

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The same seed gives the same shuffle, so the first comparison prints true. The shuffled array contains the same elements (sorting it restores the original), and shuffle leaves deck untouched. sample(3) never returns the same position twice, so a three-card hand has no duplicates as long as the deck has none. The exact order depends on the seed and the Ruby version, so test the properties (size, membership, uniqueness) instead of hard-coding a shuffled result. See Random Numbers and Math for more.

Choosing the right method

You want Use
Groups where order does not matter combination(n)
Orderings where order matters permutation(n)
Every pairing across lists product
Pages or batches each_slice(n)
Neighbours or moving windows each_cons(n)
Rows to columns transpose
Two lists side by side zip
Shift positions around a ring rotate(n)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many results does [1, 2, 3, 4].combination(2).to_a contain?

    Choosing 2 of 4 with order ignored gives 6 pairs. 12 would be the number of permutations of size 2.
  2. 2. What is the difference between each_slice(2) and each_cons(2) on [1, 2, 3, 4]?

    each_slice cuts the list into non-overlapping chunks, while each_cons slides a window one step at a time.
  3. 3. What happens when you call transpose on [[1, 2, 3], [4, 5]]?

    transpose needs equal-length rows. Ruby raises IndexError with the message element size differs (2 should be 3).
  4. 4. Why is (1..20).to_a.permutation.to_a a bad idea?

    The number of permutations is n factorial. Use the lazy enumerator with first or find, or a smarter algorithm.
  5. 5. How do you make shuffle give the same order on every run?

    A Random object created with a fixed seed produces a repeatable sequence, so shuffle(random: Random.new(42)) is repeatable.

Summary

  • combination(n) ignores order, permutation(n) respects it, and the repeated_ versions allow an element to be reused.
  • product pairs every element of several lists; its size is the product of the list sizes.
  • each_slice(n) makes non-overlapping chunks; each_cons(n) makes overlapping windows for neighbour comparisons.
  • transpose swaps rows and columns and raises IndexError on ragged rows; zip interleaves lists and pads with nil.
  • rotate(n) shifts elements around a ring and cycle repeats forever (stop it with first or break).
  • Pass random: Random.new(seed) to shuffle and sample for repeatable results.
  • Counts explode quickly, so keep enumerators lazy and avoid to_a on big inputs.

Next: Slices and Indexing in Depth