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.

$\endgroup$
2

11 Answers 11

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

Speaking of "common operation":

 Table[lst[[;; i]], {i, Length@lst}]
$\endgroup$
6
  • $\begingroup$ I was playing with a pattern based solution, +1 for ReplaceList. $\endgroup$ 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
    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
    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
    Dec 18, 2012 at 20:27
  • 1
    $\begingroup$ @rcollyer Be careful with MapAt though. $\endgroup$ 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}}

$\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, # != {} &]
$\endgroup$
13
  • 2
    $\begingroup$ Why are you using MapIndexed? Why not Subsets[list, #, 1][[1]]& /@ Range[Length@list]? It seems cleaner. $\endgroup$
    – rcollyer
    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
    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$ 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
    Dec 18, 2012 at 20:39
  • $\begingroup$ FoldList by itself works. $\endgroup$
    – rcollyer
    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}} *)
$\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$ 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
    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
    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
    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$ 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...

$\endgroup$
6
$\begingroup$

A variant using Partition:

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

A joke solution:

Outer[Take, {{a, b, c, d, e}}, Range[5], 1] // First
$\endgroup$
5
$\begingroup$
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}}

$\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}]
$\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

$\endgroup$
2
$\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}}*)
$\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.