# Output the Military Order [duplicate]

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


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.

• 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. Feb 24 '16 at 18:14
• So the lists themselves have to be sorted, but can the list of lists be in any order? Feb 24 '16 at 18:17
• Five answers and no upvotes? Come on! Feb 24 '16 at 19:02
• Please don't downvote challenges just because some languages have built-ins for them.
– Lynn
Feb 24 '16 at 19:02
• Very closely related. I think one of them should be closed as a dupe of the other. Feb 26 '16 at 18:46

f 0=[[]]
f n=[id,(++[n])]<*>f(n-1)
tail.f

• Could you explain this? Feb 25 '16 at 13:58
• [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 '16 at 14:18
• Cool .................. +1 Feb 25 '16 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


# Jelly, 4 bytes

RŒPḊ


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

• 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? Feb 24 '16 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 '16 at 18:51
• ŒP (or rather, the function iterable it uses) had a stupid bug. ŒPḊ should have worked without the R (and does now). Feb 24 '16 at 19:03

## Pyth, 149 4 bytes

tySQ


Try it here!

Thanks @FryAmTheEggman for showing me the y function :)

• @FryAmTheEggman I knew that function was somewhere but I didn't bother looking through the docs for it...
– Blue
Feb 24 '16 at 18:17

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


The function (:) 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(:)[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.

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

• Do we ignore byte contributions from Slot and Function tokens when scoring Mathematica codes here? Feb 24 '16 at 23:35
• @IPoiler This uses Composition to prevent the need for a Function. Feb 25 '16 at 1:14
• @LegionMammal978 It still does nothing in this form without at least a Prefix token. Feb 25 '16 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 &. Feb 25 '16 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? Feb 25 '16 at 14:52

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. • 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 '16 at 19:00 • @Lynn: no, I don't mind, please post. – nimi Feb 24 '16 at 19:05 # GAP, 21 bytes Combinations([1..n]);  Not really a programming accomplishment, but it also includes the empty ordering... ## 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. # 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],[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]]  # 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  ## 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.

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

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

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

## Seriously, 11 bytes

,R;╗╜╧iMi


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;╗╜╧iMi
,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



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

# 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)]

• 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)]. Feb 24 '16 at 19:59

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


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