Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Given

lst = {a, b, c, d}

I'd like to generate

{{a}, {a, b}, {a, b, c}, {a, b, c, d}}

but using built-in functions only, such as Subsets, Partitions, Tuples, Permutations or any other such command you can choose. But it has to be done only using built-in commands. You can use a pure function, if inside a built-in command, i.e. part of the command arguments. That is OK.

It is of course trivial to do this by direct coding. One way can be

lst[[1 ;; #]] & /@ Range[Length[lst]]
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}}  *)

or even

LowerTriangularize[Table[lst, {i, Length[lst]}]] /. 0 -> Sequence @@ {}
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}}  *)

But I have the feeling there is a command to do this more directly as it looks like a common operation, but my limited search could not find one so far.

Sorry in advance if this was asked before. Searching is hard for such general questions.

share|improve this question
3  
How about something like Rest@FoldList[Append, {}, {a, b, c, d}]? More succinctly, FoldList[Append,{First@#},Rest[#]]&[{a,b,c,d}] –  Leonid Shifrin Dec 18 '12 at 17:40
    
    
Somewhat related: mathematica.stackexchange.com/q/7511/121 –  Mr.Wizard Dec 19 '12 at 2:19

8 Answers 8

up vote 17 down vote accepted
 lst={a,b,c,d};
 ReplaceList[lst,{x__, ___} :> {x}]

Speaking of "common operation":

 Table[lst[[;; i]], {i, Length@lst}]
share|improve this answer
    
I was playing with a pattern based solution, +1 for ReplaceList. –  image_doctor Dec 18 '12 at 19:27
2  
+1, there's your 20k, btw. I've always had trouble with ReplaceList, and for me it is the second most annoying function that sounds useful. The most annoying being MapAt ... Although, I've more success with MapAt than ReplaceList. –  rcollyer Dec 18 '12 at 19:53
    
@rcollyer, @image_doctor, Nasser, thanks for the votes. Rcollyer, for me too -- it always takes several attempts until I get MapAt and ReplaceList right. And, i don't remember ReplaceList winning any speed contests. –  kguler Dec 18 '12 at 20:12
    
I found Position is a great way to get MapAt to behave itself, provided you can figure out how to specify what positions you need ... –  rcollyer Dec 18 '12 at 20:27
    
@rcollyer Be careful with MapAt though. –  Leonid Shifrin Dec 18 '12 at 20:29

This is not a built-in function to do it but it fits the criteria of only using buil-in functions. It avoids using patterns, mapping constructs and such things.

Maybe in the future ListCorrelate can accepts functions instead of heads (e.g. applying Plus to a list by default). I think that would make it more useful (but I am a beginner Mathematica user, so who am I to hold such opinions).

lst = {a, b, c, d};
DeleteCases[
 ListCorrelate[lst, ConstantArray[1, Length@lst], 1, 0, Times, 
  List], 0, {2}]
share|improve this answer

A joke solution:

Outer[Take, {{a, b, c, d, e}}, Range[5], 1] // First
share|improve this answer

A variant using Partition:

First[Partition[list,#]]& /@ Range@Length@list
share|improve this answer

What about Accumulate:

Function[lst, {{lst[[1]]}}~Join~Rest[Accumulate[lst] /. Plus -> List]]@{a, b, c, d, e}

Unfortunately it doesn't accept a custom function other than Plus and will not work for numerical list...

share|improve this answer

I am not sure this wins any speed contests, but it is a purely functional solution:

FoldList[#1~Join~{#2} &, {First@#}, Rest@#]& @ {a, b, c, d, e}
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}, {a, b, c, d, e}} *)
share|improve this answer
    
Ok, since you posted this, I am liberated from doing that (I gave it in comments to the question), and can happily upvote : +1. –  Leonid Shifrin Dec 18 '12 at 21:03
    
+1, a variation: FoldList[Flatten@{##} &, {First@list}, Rest@list]? or FoldList[Sequence @@@ {##} &, {First@list}, Rest@list]? –  kguler Dec 18 '12 at 21:06
    
@kguler I'd migrate list outside of FoldList, but I hate writing more than I have too. –  rcollyer Dec 18 '12 at 21:15
    
@LeonidShifrin teach me to look at the comments before I post something ... Speed wise, though, is Join or Append faster. What about kguler's alternatives? –  rcollyer Dec 18 '12 at 21:16
    
I think @kguler's use of ReplaceList is very elegant. For generic lists, should be quite fast. For packed arrays, Join and Append should be faster, since ReplaceList can not make use of those and will likely unpack. –  Leonid Shifrin Dec 18 '12 at 21:20

A variant using Take.

list~Take~# & /@ Range@Length@list

{{a}, {a, b}, {a, b, c}, {a, b, c, d}}

One using NestList:

NestList[Most, list, Length@list - 1]

{{a, b, c, d}, {a, b, c}, {a, b}, {a}}

share|improve this answer

Subsets takes an optional 3rd argument as Subsets[list, {n}, k] that gives you the kth sublist of length n. Since your sublists are in sequence, you'll always need k = 1. You can then use this as:

MapIndexed[First@Subsets[list, #2, 1] &, list]
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}} *)

Another alternative would be:

Reverse@Most@NestWhileList[Most, list, # != {} &]
share|improve this answer
    
Why are you using MapIndexed? Why not Subsets[list, #, 1][[1]]& /@ Range[Length@list]? It seems cleaner. –  rcollyer Dec 18 '12 at 20:10
1  
"Cleaner" is subjective and in this case, I positively dislike having to use Range@Length@foo when I don't have to. Far cleaner to use MapIndexed and ignore #1 –  rm -rf Dec 18 '12 at 20:20
    
+1. But the real clean solution here is to use linked lists, since all of the suggested ones have quadratic complexity in the length of the list. –  Leonid Shifrin Dec 18 '12 at 20:28
    
@LeonidShifrin I thought of something like Flatten /@ Rest@FoldList[List, {}, {a, b, c, d}], but it was similar to your solution above and was hoping you'd post it –  rm -rf Dec 18 '12 at 20:39
    
FoldList by itself works. –  rcollyer Dec 18 '12 at 20:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.