Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

In almost every row nowadays, the people tends to order themselves as militaries would do.

Challenge

Suppose 4 people where:

  • person 1 has priority against person 2, 3 and 4,
  • person 2 has priority against person 3 and 4,
  • person 3 has priority against person 4,
  • person 4 has the lowest priority.

Then, when ordering those 1...4 people in a row, the possibilities are:

1
2
3
4
1 2
1 3
1 4
2 3
2 4
3 4
1 2 3
1 2 4
1 3 4
2 3 4
1 2 3 4

Your mission is:

Given as input the number N of people. Output all the possibilities for 1...N people in the military order.

Since this is , then the shotest answer in bytes wins!


Input can be integer or string, followed by optional newline/whitespace, or an argument to your function. You can assume 1<=N<=10.

The output should be every sequence in a row, in any order. For each row, output a list/array or any other valid way for the numbers in military order.

share|improve this question

marked as duplicate by FryAmTheEggman, Mego, mbomb007, Zach Gates, Downgoat Feb 27 at 0:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3  
Just so you know, this is extremely trivial in many languages, Pyth for example has a builtin that does almost exactly this. These are just the subsets of [1..N] in sorted order. – FryAmTheEggman Feb 24 at 18:14
1  
So the lists themselves have to be sorted, but can the list of lists be in any order? – Martin Ender Feb 24 at 18:17
1  
Five answers and no upvotes? Come on! – Luis Mendo Feb 24 at 19:02
10  
Please don't downvote challenges just because some languages have built-ins for them. – Lynn Feb 24 at 19:02
4  
Very closely related. I think one of them should be closed as a dupe of the other. – FryAmTheEggman Feb 26 at 18:46

20 Answers 20

up vote 5 down vote accepted

Pyth, 14 9 4 bytes

tySQ

Try it here!

Thanks @FryAmTheEggman for showing me the y function :)

share|improve this answer
    
@FryAmTheEggman I knew that function was somewhere but I didn't bother looking through the docs for it... – muddyfish Feb 24 at 18:17

Haskell, 41 bytes

f 0=[[]]
f n=[id,(++[n])]<*>f(n-1)
tail.f
share|improve this answer
1  
Could you explain this? – Caridorc Feb 25 at 13:58
1  
[f, g] <*> [X, Y, Z] is [f X, f Y, f Z, g X, g Y, g Z] in Haskell. To form all subsequences of [1..n], I take all subsequences of [1..n-1], twice, and append [n] to each element of the second copy. – Lynn Feb 25 at 14:18
    
Cool .................. +1 – Caridorc Feb 25 at 14:19

Japt, 5 bytes

(Yes, this is me, ETHproductions.)

1òU à

Test it online! (This version has a few extra bytes to pretty-print the output.)

How it works

      // Implicit: U = input integer
1òU   // Generate the inclusive range [1..U].
à     // Generate all combinations of this range.
      // Implicit: output last expression
share|improve this answer

Jelly, 4 bytes

RŒPḊ

Basically the same thing as Pyth. Range, ŒPower set, equeue. Try it here!

share|improve this answer
    
I had come up with the same thing, but was rather surprised that Jelly had 2 byte operators, I thought I had made a mistake typing it so I didn't post. Oh well :P Do you know if Jelly is actually out of 1 byte operations? – FryAmTheEggman Feb 24 at 18:49
    
Nope, it isn't, yet! But Dennis is still running into features more important to have around than power set... ^^ – Lynn Feb 24 at 18:51
2  
ŒP (or rather, the function iterable it uses) had a stupid bug. ŒPḊ should have worked without the R (and does now). – Dennis Feb 24 at 19:03

Haskell, 38 bytes

f n=init$filter(>0)<$>mapM(:[0])[1..n]

The function (:[0]) takes x to [x,0]. Doing mapM of this onto [1..n] takes the Cartesian product of [[1,0],[2,0],...,[n,0]], giving each subset of [1..n] with missing elements replaced by 0.

*Main> mapM(:[0])[1..3]
[[1,2,3],[1,2,0],[1,0,3],[1,0,0],[0,2,3],[0,2,0],[0,0,3],[0,0,0]]

Finally, zeroes are filtered out from each list and the empty list at the end is removed.

share|improve this answer
    
+1, I forgot mapM is in Prelude! – Lynn Feb 25 at 14:13
    
You have me beat, 39 chars: f n=[[z|z<-[x..y]]|x<-[1..n],y<-[x..n]] – recursion.ninja Feb 25 at 19:31
    
@recursion.ninja That only gives continuous sub-lists, not all subsequences. It doesn't give [1,3]. – xnor Feb 26 at 20:44

Mathematica, 20 bytes

Rest@*Subsets@*Range

Composes an unnamed function that takes an integer and returns a list of lists. We need Rest because Subsets contains the empty list.

share|improve this answer
    
Do we ignore byte contributions from Slot and Function tokens when scoring Mathematica codes here? – IPoiler Feb 24 at 23:35
    
@IPoiler This uses Composition to prevent the need for a Function. – LegionMammal978 Feb 25 at 1:14
    
@LegionMammal978 It still does nothing in this form without at least a Prefix token. – IPoiler Feb 25 at 2:34
    
@IPoiler like any unnamed function submission, this is an expression that evaluates to a function which can then be used exactly like a pure function written with &. – Martin Ender Feb 25 at 8:11
    
@MartinBüttner I don't see why it's valid to omit @ in the byte count when @ isn't considered part of the input format. This seems obvious when you consider other languages are including optional flags in byte counts. What then should be the scores for submissions like Foo@@ and Foo/@ which can be applied directly to input? Am I overcounting bytes on my anonymous function submissions by including the implicit Prefix? – IPoiler Feb 25 at 14:52

Haskell, 44 bytes

import Data.List
f x=tail$subsequences[1..x]

As so often, the import ruins the score.

tail removes the first list (which is always the empty list) of all subsequences of the list from 1 to x.

share|improve this answer
    
It turns out f 0=[[]];f n=[id,(++[n])]<*>f(n-1);tail.f is three bytes shorter! (Do you mind if I post that as a separate answer?) – Lynn Feb 24 at 19:00
    
@Lynn: no, I don't mind, please post. – nimi Feb 24 at 19:05

CJam, 18 bytes

L]ri{)1$f++}/:$1>p

Test it here.

Uses a trick I learned from Dennis once upon a time to generate the powerset.

share|improve this answer

Julia, 42 bytes

N->[collect(combinations(1:N,i))for i=1:N]

This is an anonymous function that accepts an integer and returns an array of arrays. We simply get the combinations of size i for each i from 1 to N. Because of the way combinations is implemented in Julia, the arrays are already sorted.

Example:

julia> f=N->[collect(combinations(1:N,i))for i=1:N]
(anonymous function)

julia> f(4)
4-element Array{Any,1}:
 [[1],[2],[3],[4]]                    
 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
 [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]    
 [[1,2,3,4]]
share|improve this answer

Python 3, 92

Saved 17 bytes thanks to mathmandan.

Stupid itertools and its long function names.

from itertools import*
lambda i:[y for n in range(i)for y in combinations(range(1,i+1),n+1)]
share|improve this answer
    
I think len(x) is just i, isn't it? So after the import statement, how about lambda i:[y for n in range(1,i+1)for y in combinations(range(1,i+1),n)]? Or better, lambda i:[y for n in range(i)for y in combinations(range(1,i+1),n+1)]. – mathmandan Feb 24 at 19:59
    
@Seeq Excellent points... :) – mathmandan Feb 24 at 20:23

MATLAB / Octave, 49 bytes

function f(n)
for r=1:n,disp(nchoosek(1:n,r));end

This generates the vector [1,2,...,n]. Then generates all subsets with 1 element, all subsets with 2 elements, ..., with n elements.

Example run:

>> f(4)
     1
     2
     3
     4
     1     2
     1     3
     1     4
     2     3
     2     4
     3     4
     1     2     3
     1     2     4
     1     3     4
     2     3     4
     1     2     3     4
share|improve this answer

CJam (18 bytes)

ri)e!{_0#<$}%_&1>`

is equivalent to

ri)e!_0f#.<:$_&1>`

and very different to

ri,:)Maf+:m*:e_);`

but they're all the same length.

share|improve this answer

R, 36 bytes

function(x)sapply(1:n,combn,x=n,s=F)

combn returns all cmbinations of x taken m at a time. if x is a single integer, returns all combinations of 1:n. sapply required to vectorize over m. s=F stops the results being simplified and thus returns a list as required.

share|improve this answer

GAP, 21 bytes

Combinations([1..n]);

Not really a programming accomplishment, but it also includes the empty ordering...

share|improve this answer

Python, 69 bytes

def f(n):print[[j+1for j in range(n)if 1&i>>j]for i in range(1,1<<n)]

The key here is that we're really just asking, in order, which bits are 1 for each number i in the set of all n-bit numbers.

share|improve this answer

JavaScript (ES7 proposed), 78 bytes

n=>[for(i of Array(2**n).keys())if(i)[for(j of Array(n).keys())if(i&1<<j)j+1]]

Based on @MegaTom's binary power set answer. Only works up to n=32.

share|improve this answer

Seriously, 11 bytes

,R;╗`╜╧i`Mi

This code is super gross. I'm disgusted at how it turned out. I really need to work on Seriously 2. Actually I'm just an idiot. Still need to work on Seriously 2, though.

Try it online!

Explanation:

,R;╗`╜╧i`Mi
,R;╗         get two copies of range(1, input+1), store one in register 0
    `   `M   map:
     ╜╧        n-length permutations of range(1, input+1)
       i       flatten list
          i  flatten list
share|improve this answer

MATL, 11 bytes

2i^q:B!"@!f

Try it online!

2i^q    % 2^n-1, where n is the input number
:       % range [1,...,2^n-1]
B       % convert to binary. Gives 2D array where each number is a row
!       % transpose
"       % for each column
  @     %   push that column
  !     %   transpose into a row
  f     %   indices of nonzero elements
        % implicit end for each
        % implicitly display stack contents

As an example, with input 3, the code 2i^q: gives the array [1 2 3 4 5 6 7]. Then B! gives the 2D array

[ 0 0 0 1 1 1 1;
  0 1 1 0 0 1 1;
  1 0 1 0 1 0 1 ]

and then the loop "@!f gives 3 in the first iteration, 2 in the second, [2 3] in the third etc.

share|improve this answer

Ruby, 47 bytes

->n{(r=*1..n).flat_map{|x|[*r.combination(x)]}}
->n{
(r=*1..n)         # set r to [1, 2, 3, ..., n-1, n]
.flat_map{|x|     # map and then flatten resulting array one level...
[*                # a golfy variant of .to_a
r.combination(x)  # combination as in combinatorics, conveniently already sorted
]}}
share|improve this answer

Ruby, 50 bytes

A shorter ruby solution exists, using a completely different method.

This solution uses the unique idea of looking at all the numbers from 1 to 2^n-1 and getting a list of which bits are 1, for each number.

->n{(1...2**n).map{|i|(1..n).reject{|a|i[a-1]<1}}}
share|improve this answer

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