# Array Sandwiches

You have several arrays, named $$\A_1, A_2, ... , A_n\$$, each sorted in ascending order. Every item in the array will be a 32-bit integer.

A sandwich is a set of indices $$\j_1, j_2, ... , j_n\$$ such that $$\A_1[j_1] ≤ A_2[j_2] ≤ ... ≤ A_n[j_n]\$$. $$\A_i[0]\$$ is the first element of $$\A_i\$$.

Given some arrays, output every possible sandwich that you can have from those arrays, separated by a newline.

If there is somehow a built-in function which does this in your language, don't use it.

Input can be given in any way, output must be separated with whitespace, but can given in any order.

Test Case:

[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]


Output:

0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2


Test Case:

[[10, 20, 30], [1, 2, 3]]


Output:

Shortest code wins.

• What values can the arrays contain? Only positive integers? Sep 23, 2012 at 18:47
• @IlmariKaronen: They will contain negative integers as well. Sep 23, 2012 at 21:08
• @PeterTaylor: For simplicity, they will be 32-bit integers. Sep 23, 2012 at 21:46
• @DavidCarraher: It's the next test case. I should make it more clear. Sep 23, 2012 at 22:50
• Thanks. Now I see that my current solution only works for arrays of 3 elements. I'll have to work a bit more to generalize it. Sep 23, 2012 at 23:22

## APL (33)

↑1-⍨B/⍨{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B←,⍳⊃∘⍴¨A←⎕


Input is read from the keyboad, but it must be given as an APL list, i.e.

(1 5 7 10) (2 6 6 8 12) (4 5 9)


Explanation:

• B←,⍳⊃∘⍴¨A←⎕: A is evaluated input, B is all possible sets of indices in the lists given in A.
• {(⍳⍴A)∘≡⍋⍵⌷¨A}¨B: for each set of indices, get the values from the lists (⍵⌷¨A) and see if they are sorted ((⍳⍴A)∘=⍋)
• B/⍨: select from B all sets of indices where the previous expression was true (i.e. all the sandwiches)
• 1-⍨: subtract one from all indices, because this question assumed 0-based arrays and APL-arrays are 1-based by default.
• ↑: arrange the list of sets of indices as a matrix (so each set is on its own line)

## GolfScript, 51 chars

~:A{,}%{*}*,{A{,.@.@/\@%}%\;}%{:k,,{.A=\k==}%.$=},  Example input (on stdin): [[1 5 7 10] [2 6 6 8 12] [4 5 9]]  Example output (to stdout): [[0 0 0] [0 0 1] [0 0 2] [0 1 2] [1 1 2] [0 2 2] [1 2 2] [0 3 2] [1 3 2] [2 3 2]]  (Note that input must be given without commas, otherwise the program will most likely crash.) I guess I should add some explanation about how this code works: • ~:A just evaluates the input as GolfScript code and assigns the result (an array of arrays) to A. It also leaves a copy of A on the stack for the next step. • {,}% replaces each sub-array with its length, and {*}* multiplies those lengths together, giving the total number of possible sandwich candidates. This number is then converted by , to an array of that many successive integers starting from 0. • {A{,.@.@/\@%}%\;}% converts each number into a the corresponding sandwich candidate (i.e. an array of valid indices into each sub-array in A). For example, given the input above, 0 would map to [0 0 0], 1 to [1 0 0], 2 to [2 0 0], 3 to [3 0 0], 4 to [0 1 0] and so on. (Figuring out exactly how the code accomplishes that is left as an exercise for the interested reader.) • {:k,,{.A=\k==}%.$=}, filters the sandwich candidates by mapping each of them to the corresponding elements of the sub-arrays of A (so that e.g. [0 0 0] would yield [1 2 4], [1 0 0] would yield [5 2 4], and so on, for the input above), sorting the resulting array and comparing it with an unsorted copy. If they are equal, the array was already sorted, and thus the candidate is indeed a sandwich.

• Finally,  just turns the filtered array of sandwiches into a string for output.

• They must be seperated by whitespace, so spaces or tabs work as well. Sep 23, 2012 at 21:10
• OK, I've changed the output format. Sep 23, 2012 at 21:25

# Mathematica, 120 130 bytes

## Edit

This version works with arrays of varying sizes.

l = List;
g = Grid@Cases[Outer[l, Sequence @@ MapIndexed[l, #, {2}], 1]~Flatten~(Length[#] - 1),
x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1] &


## Usage

g@{{10, 20, 30}, {1, 22, 3}}
g@{{1, 5, 7, 10}, {2, 6, 6, 8, 12}, {4, 5, 9}}
g@{{10, 20, 30}, {1, 2, 3}}
g@{{1, -2, 3}, {-12, -7, 8, 9, 6}, {3, 99, 9}, {100, 10, -23}, {90, 10}}


## Explanation

Using the first example from above,

a = {{10, 20, 30}, {1, 22, 3}}


MapIndexed  sets indices for all the elements. N.B.: Mathematica begins counting with 1. (We'll later take that into account.)

MapIndexed[l, a, {2}]


{{{10, {1, 1}}, {20, {1, 2}}, {30, {1, 3}}}, {{1, {2, 1}}, {22, {2, 2}}, {3, {2, 3}}}}

Outer generates all lists, each a candidate as a sandwich array, and the indices of their elements; % contains the results from the prior output. The numbers, 10 and 22 which I highlighted after they were output, refer to a sandwich array {10,22} that has yet to be identified as such.

Outer[l, Sequence @@ %, 1]~Flatten~(Length[a] - 1)


{{{10, {1, 1}}, {1, {2, 1}}}, {{10, {1, 1}}, {22, {2, 2}}}, {{10, {1, 1}}, {3, {2, 3}}}, {{20, {1, 2}}, {1, {2, 1}}}, {{20, {1, 2}}, {22, {2, 2}}}, {{20, {1, 2}}, {3, {2, 3}}}, {{30, {1, 3}}, {1, {2, 1}}}, {{30, {1, 3}}, {22, {2, 2}}}, {{30, {1, 3}}, {3, {2, 3}}}}

Cases tests each element of the above to determine whether a LessEqual (less than or equal) relation holds.  The results shown below are those instances in which array sandwiches were detected. Once again, I highlighted {10,22} in the output.

Cases[%, x_ /; LessEqual @@ x[[All, 1]] == True]


{{{10, {1, 1}}, {22, {2, 2}}}, {{20, {1, 2}}, {22, {2, 2}}}}

%% refers to the penultimate results. :>, [ RuleDelayed]  returns thos parts of the instances of interest, namely, the indices of the array sandwiches.  -1 corrects for the fact that Mathematica begins arrays with 1 instead of 0.

Cases[%%, x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1]


{{0, 1}, {1, 1}}

Grid displays the results in a grid. The first row 0 1 means the that element 0 from the first sublist (i.e. 10) and the element 1 from the second sublist (i.e. 22) constitute the first sandwich array that was found.

Grid@%


0 1

1 1

• I dislike this answer since you artificially simplify your answer by fixing the number arrays. Sep 24, 2012 at 13:32
• If you mean that it only works for arrays of 3 "rows", I share your dislike. The problem has to do with enabling LessEqual to work with arrays of indeterminate size. There may be other instances where the same assumption impedes generality. When I get a chance, I'll generalize the approach. Sep 24, 2012 at 13:49
• @FUZxxl I was able to generalize the approach. Take a look. Sep 24, 2012 at 19:24
• @DavidC Why did you rollback my edit? Looks like the x_ /; etc. part is code and should be in a code block? Feb 11, 2021 at 4:10
• you are right. I rolled back to your version. Feb 12, 2021 at 3:11

# Jelly, 10 bytes

J€Œpị"ṢƑ¥Ƈ


Try it online!

This uses 1-indexing which is the default for Jelly. +2 bytes to use 0-indexing.

## How it works

J€Œpị"ṢƑ¥Ƈ - Main link. Takes a 2d array A on the left
€         - Over each subarray:
J          -   Replace the subarray with its indices
Œp       - Take the Cartesian product of these indices
¥Ƈ - Keep the indices for which the following is true:
ị"     -   Index into each subarray of A
ṢƑ   -   The resulting elements are in ascending order?


## R - 89 chars

i=do.call(expand.grid,lapply(x,seq_along))
i[apply(diff(t(mapply([,x,i)))>=0,2,all),]-1


where

x = list(c(1, 5, 7, 10), c(2, 6, 6, 8, 12), c(4, 5, 9))


or

x = list(c(10, 20, 30), c(1, 2, 3))


# Python, 149141 140

import itertools as I;x=input();r=range;print[p for p in I.product(*map(r,map(len,x)))if all(x[i][p[i]]<=x[i+1][p[i+1]]for i in r(len(x)-1))]


Python has a useful itertools library that can generate permutations. This just iterates over all possible permutations of valid indices and checks whether they satisfy the criteria.

I think I can make this shorter, still working on it.

Edit: Now all one line for your reading (in)convenience!

• r=range will save one character. Sep 25, 2012 at 23:17
• Thanks for the tip. It never occurred to me that I can alias library functions. Sep 26, 2012 at 13:48

# Python 120

f=lambda p,k=0:['%i '%j+m for j,v in enumerate(p[0])if v>=k for m in f(p[1:],v)]if p else['']
print'\n'.join(f(input()))


... still think, "enumerate" is a very long word.

## GolfScript (44 chars)

~{.,,]zip}%{{{+}+1$\/}%\;}*{2%.$=},{(;2%}%


Same input and output format as Ilmari's entry.

Demo

Rough breakdown:

Map each input row into an array of pairs [value index]

{.,,]zip}%


Fold a Cartesian product over the rows

{{{+}+1$\/}%\;}*  Filter to those whose 0th, 2nd, 4th, etc. entries are non-decreasing. {2%.$=},


Map each one down to its 1st, 3rd, 5th, etc. entries.

{(;2%}%


# 05AB1E, 20 bytes

εεN].«â€˜ʒεINèsè}¥dP


Indexing into matrices is not 05AB1E's strong suit.. :/

Try it online.

Explanation:

εεN]         #Transform the input to a list of lists of indices:
ε            # Map over each list of the (implicit) input-list:
ε           #  Map over each inner value in this list:
N          #   Push the map-index
]         # Close both maps

.«â€˜        #Create all combinations of the indices in each list:
.«           # Left-reduce the list of lists by:
â          #  Taking the cartesian product
€         # Then map over each inner list of nested lists:
˜        #  And flatten the values to a single list

ʒεINèsè}¥dP  #Filter to keep just the indices that are in ascending order
ʒ            # Filter the list of lists of indices by:
ε           #  Map over each index:
INè        #   Use the map-index itself to index into the input list of lists
sè      #   Then use the index we're mapping over to index into this list
}¥    #  After the map: get all the deltas / forward differences
d   #  Check for each that they're non-negative (>=0)
P  #  And check if this is truthy for all of them
# (after the filter, the result is output implicitly)


# Vyxal, 10 bytes

vẏΠ'?¨£iÞṠ


Try it Online!

Port of Jelly.

# Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}


# Wolfram Language (Mathematica), 30 bytes

#<=##&~Outer~##~Position~True&


Try it online!

Returns 1-indexed. For 0-indexing, add -1 (+2 bytes).

## JavaScript, 138 bytes

x=a=>(f=(a,p)=>a[0].flatMap((v,i)=>v<p?null:a[1]?(r=f(a.slice(1),v))&&r.map(j=>j&&[i,...j]):[[i]]))(a).map(i=>i?i.join(' ')+'\n':'').join('')


x = a => (f = (a, p) => a[0].flatMap(
(v, i) => v<p
? null
: a[1]
? (r = f(a.slice(1), v)) && r.map(j => j && [i, ...j])
: [[i]]
)
)(a).map(
i => i
? i.join(' ') + '\n'
: ''
).join('')


# J, 22 bytes

#&>#:[:I.(-:/:~)@>@,@{


Try it online!

Takes input as boxed lists, as J does not allow heterogeneous arrays.

• >@,@{ The open > of the flatten , of the Cartesian product {. This is just one big matrix whose rows are the elements of the Cartesian product.
• (-:/:~)@ Which of those matches itself sorted? Returns a single 0-1 boolean list.
• [:I. Indices of the ones.
• #&>#:` Convert to a mixed base number, where the bases are the lengths of the original input lists.