10
\$\begingroup\$

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.

\$\endgroup\$

marked as duplicate by FryAmTheEggman, Mego, mbomb007, Zach Gates, Downgoat Feb 27 '16 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
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Feb 24 '16 at 18:14
  • 1
    \$\begingroup\$ So the lists themselves have to be sorted, but can the list of lists be in any order? \$\endgroup\$ – Martin Ender Feb 24 '16 at 18:17
  • 1
    \$\begingroup\$ Five answers and no upvotes? Come on! \$\endgroup\$ – Luis Mendo Feb 24 '16 at 19:02
  • 10
    \$\begingroup\$ Please don't downvote challenges just because some languages have built-ins for them. \$\endgroup\$ – Lynn Feb 24 '16 at 19:02
  • 4
    \$\begingroup\$ Very closely related. I think one of them should be closed as a dupe of the other. \$\endgroup\$ – FryAmTheEggman Feb 26 '16 at 18:46

20 Answers 20

5
\$\begingroup\$

Pyth, 14 9 4 bytes

tySQ

Try it here!

Thanks @FryAmTheEggman for showing me the y function :)

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

Haskell, 41 bytes

f 0=[[]]
f n=[id,(++[n])]<*>f(n-1)
tail.f
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you explain this? \$\endgroup\$ – Caridorc Feb 25 '16 at 13:58
  • 1
    \$\begingroup\$ [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. \$\endgroup\$ – Lynn Feb 25 '16 at 14:18
  • \$\begingroup\$ Cool .................. +1 \$\endgroup\$ – Caridorc Feb 25 '16 at 14:19
8
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

Jelly, 4 bytes

RŒPḊ

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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – FryAmTheEggman Feb 24 '16 at 18:49
  • \$\begingroup\$ Nope, it isn't, yet! But Dennis is still running into features more important to have around than power set... ^^ \$\endgroup\$ – Lynn Feb 24 '16 at 18:51
  • 2
    \$\begingroup\$ ŒP (or rather, the function iterable it uses) had a stupid bug. ŒPḊ should have worked without the R (and does now). \$\endgroup\$ – Dennis Feb 24 '16 at 19:03
5
\$\begingroup\$

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.

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

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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?) \$\endgroup\$ – Lynn Feb 24 '16 at 19:00
  • \$\begingroup\$ @Lynn: no, I don't mind, please post. \$\endgroup\$ – nimi Feb 24 '16 at 19:05
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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]]
\$\endgroup\$
1
\$\begingroup\$

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)]
\$\endgroup\$
  • \$\begingroup\$ 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)]. \$\endgroup\$ – mathmandan Feb 24 '16 at 19:59
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

GAP, 21 bytes

Combinations([1..n]);

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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

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