22
$\begingroup$

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.

Improve this question
$\endgroup$
2

12 Answers 12

Reset to default
29
$\begingroup$ 
 lst={a,b,c,d};
 ReplaceList[lst,{x__, ___} :> {x}]

Speaking of "common operation":

 Table[lst[[;; i]], {i, Length@lst}]
Improve this answer
$\endgroup$
6
  • $\begingroup$ I was playing with a pattern based solution, +1 for ReplaceList. $\endgroup$
    – image_doctor
    Commented Dec 18, 2012 at 19:27
  • 2
    $\begingroup$ +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. $\endgroup$
    – rcollyer
    Commented Dec 18, 2012 at 19:53
  • $\begingroup$ @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. $\endgroup$
    – kglr
    Commented Dec 18, 2012 at 20:12
  • $\begingroup$ 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 ... $\endgroup$
    – rcollyer
    Commented Dec 18, 2012 at 20:27
  • 1
    $\begingroup$ @rcollyer Be careful with MapAt though. $\endgroup$
    – Leonid Shifrin
    Commented Dec 18, 2012 at 20:29
19
$\begingroup$

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}}

Improve this answer
$\endgroup$
17
$\begingroup$

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, # != {} &]
Improve this answer
$\endgroup$
13
  • 2
    $\begingroup$ Why are you using MapIndexed? Why not Subsets[list, #, 1][[1]]& /@ Range[Length@list]? It seems cleaner. $\endgroup$
    – rcollyer
    Commented Dec 18, 2012 at 20:10
  • 2
    $\begingroup$ "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 $\endgroup$
    – rm -rf ♦
    Commented Dec 18, 2012 at 20:20
  • $\begingroup$ +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. $\endgroup$
    – Leonid Shifrin
    Commented Dec 18, 2012 at 20:28
  • $\begingroup$ @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 $\endgroup$
    – rm -rf ♦
    Commented Dec 18, 2012 at 20:39
  • $\begingroup$ FoldList by itself works. $\endgroup$
    – rcollyer
    Commented Dec 18, 2012 at 20:41
12
$\begingroup$

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}} *)
Improve this answer
$\endgroup$
7
  • $\begingroup$ Ok, since you posted this, I am liberated from doing that (I gave it in comments to the question), and can happily upvote : +1. $\endgroup$
    – Leonid Shifrin
    Commented Dec 18, 2012 at 21:03
  • $\begingroup$ +1, a variation: FoldList[Flatten@{##} &, {First@list}, Rest@list]? or FoldList[Sequence @@@ {##} &, {First@list}, Rest@list]? $\endgroup$
    – kglr
    Commented Dec 18, 2012 at 21:06
  • $\begingroup$ @kguler I'd migrate list outside of FoldList, but I hate writing more than I have too. $\endgroup$
    – rcollyer
    Commented Dec 18, 2012 at 21:15
  • $\begingroup$ @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? $\endgroup$
    – rcollyer
    Commented Dec 18, 2012 at 21:16
  • $\begingroup$ 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. $\endgroup$
    – Leonid Shifrin
    Commented Dec 18, 2012 at 21:20
10
$\begingroup$

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...

Improve this answer
$\endgroup$
6
$\begingroup$

A variant using Partition:

First[Partition[list,#]]& /@ Range@Length@list
Improve this answer
$\endgroup$
5
$\begingroup$

A joke solution:

Outer[Take, {{a, b, c, d, e}}, Range[5], 1] // First
Improve this answer
$\endgroup$
5
$\begingroup$

Update

Rest@SequenceFoldList[Flatten@*List, {{}}, lst]

(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}} *)

Original Answer

FromLetterNumber@Range@Range[4]

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

Edit

On looking at this answer by Carl Woll (see also part-2 of the answer by image_doctor below).

And see also the comment by kglr to this answer by rcollyer.

FoldList[Flatten[{##}] &, Nothing, {a, b, c, d}]

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

Improve this answer
$\endgroup$
3
$\begingroup$

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}]
Improve this answer
$\endgroup$
3
$\begingroup$

Using Cases and Accumulate:

list = {a, b, c, d};
Cases[Accumulate[list], s_ :> If[AtomQ[s], {s}, List @@ s]]

(*{{a}, {a, b}, {a, b, c}, {a, b, c, d}}*)

Also, using Drop:

Reverse[Table[Drop[#, -i], {i, 0, Length@# - 1}]] &@list

(*{{a}, {a, b}, {a, b, c}, {a, b, c, d}}*)

Also, usin TakeList:

Table[Sequence @@ TakeList[#, {i}], {i, Length@#}] &@list

(*{{a}, {a, b}, {a, b, c}, {a, b, c, d}}*)
Improve this answer
$\endgroup$
3
$\begingroup$

Using AccumulateApply by Ian Ford and Jon McLoone

AccumulateApply = ResourceFunction["AccumulateApply"];

list = {a, b, c, d};

AccumulateApply[List, list]

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

Improve this answer
$\endgroup$
2
$\begingroup$ 
list = {a, b, c, d};

MapAt[List, 1] @ MapApply[List] @ Accumulate @ list

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

MapApply came with V 13.1

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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