"Pyramidizing" an array/list (in Ruby, but general solutions could probably be implemented)

I'm not sure what the best word to use here. By "pyramidizing", I mean:

[1,2,3,4].pyramidize  # => [1,1,1,1,2,2,2,3,3,4]
["a","b","c","d"].pyramidize  # => ["a","a","a","a","b","b","b","c","c","d"]

To represent visu开发者_运维问答ally, it could be thought of as:

[ 1,1,1,1,
   2,2,2,
    3,3,
     4    ]

Is there a way to do this that maximizes elegance? A most ruby-like way?

I came across the "need" to do this in a project of mine. After thinking about it, I gave up and decided to work around the problem in an ugly way. I was wondering if there was a pretty way to do this. So far, to do it directly, I've ended up making a separate array for each index and stretching out each array the appropriate length and combining them together. But I don't know how to do this so it looks pretty; my solution is pretty ugly.

Added code golf tag because any solution in one line would probably make my day, but it doesn't have to be.

It doesn't really matter if your solution makes the first index the "base" of the pyramid, or the last index, because I could just reverse the array before running it.

Requires the new iterator fanciness in Ruby 1.9.

class Array
  def pyramidize
    reverse.map.with_index do |object, index|
      [object] * (index + 1)
    end.flatten.reverse
  end
end

[1,2,3,4].pyramidize
 => [1, 1, 1, 1, 2, 2, 2, 3, 3, 4] 
["a","b","c","d"].pyramidize
 => ["a", "a", "a", "a", "b", "b", "b", "c", "c", "d"] 

irb(main):001:0> [2,1,3,5].flat_map.with_index{|i,j|[i]*(j+1)}
=> [2, 1, 1, 3, 3, 3, 5, 5, 5, 5]
irb(main):002:0> [1,2,3,4].flat_map{|i|[i]*i}
=> [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

I'm not sure if you want to use the value of the list or the index to determine how much the list should repeat, but a simple solution in python that can probably transfer to ruby easily:

>>> import operator
>>> input = range(6)
>>> reduce(operator.add, [[i]*idx for idx, i in enumerate(input)])
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]

Update

Oh and to invert the counts:

>>> import operator
>>> input = range(1, 6)
>>> reduce(operator.add, [[i]*(max(input) - idx) for idx, i in enumerate(input)])
[1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5]

And of course you reversed the list in one of your examples:

>>> import operator
>>> input = range(1, 6)
>>> reduce(operator.add, [[i]*(max(input) - idx) for idx, i in enumerate(input)])[::-1]
[     5,
     4, 4, 
   3, 3, 3,
  2, 2, 2, 2,
 1, 1, 1, 1, 1]

FWIW, this is a mathy way of doing it:

>>> A = [1, 2, 3, 4]
>>> [ A[int((sqrt(8*k+1)-1) / 2)] for k in range(len(A)*(len(A)+1) / 2) ]
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

Admittedly, the use of sqrt is pretty ugly.

Here is another way to do it in Python

>>> A=[1,2,3,4]
>>> [y for i,x in enumerate(A) for y in [x]*(len(A)-i)]
[1, 1, 1, 1, 2, 2, 2, 3, 3, 4]

But it's nicer not to create all those temporary lists

>>> from itertools import repeat
>>> [y for i,x in enumerate(A) for y in repeat(x, len(A)-i)]
[1, 1, 1, 1, 2, 2, 2, 3, 3, 4]