(Adaptado do Problema C do primeiro qualificador do Concurso de Programação ACM de 2012/2013 )

Você tem várias matrizes, denominadas A ₁ , A ₂ , ..., A _n , cada uma classificada em ordem crescente. Cada item da matriz será um número inteiro de 32 bits.

Um sanduíche é um conjunto de índices j ₁ , j ₂ , ..., j _{n de} modo que A ₁ [j ₁ ] ≤ A ₂ [j ₂ ] ≤ .... ≤ A _n [j _n ].
A _i [0] é o primeiro elemento de A _i .

Dadas algumas matrizes, produza todos os sanduíches possíveis que você puder obter dessas matrizes, separados por uma nova linha.

Se houver alguma função interna que faça isso no seu idioma, não a utilize.

A entrada pode ser fornecida de qualquer forma, a saída deve ser separada por espaços em branco, mas pode ser fornecida em qualquer ordem.

Caso de teste:
[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]

Resultado:

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

Caso de teste:
[[10, 20, 30], [1, 2, 3]]

Resultado:

O menor código vence.

APL (33)

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

A entrada é lida no keyboad, mas deve ser fornecida como uma lista de APL, ou seja,

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

Explicação:

• B←,⍳⊃∘⍴¨A←⎕: A é entrada avaliada, B é todos os conjuntos possíveis de índices nas listas fornecidas em A.
• {(⍳⍴A)∘≡⍋⍵⌷¨A}¨B: para cada conjunto de índices, obtenha os valores das listas ( ⍵⌷¨A) e veja se eles estão classificados ( (⍳⍴A)∘=⍋)
• B/⍨: selecione de B todos os conjuntos de índices onde a expressão anterior era verdadeira (ou seja, todos os sanduíches)
• 1-⍨: subtraia um de todos os índices, porque esta pergunta assumiu que matrizes baseadas em 0 e matrizes de APL são baseadas em 1 por padrão.
• ↑: organize a lista de conjuntos de índices como uma matriz (para que cada conjunto esteja em sua própria linha)

Mathematica 120 130

Editar

Esta versão funciona com matrizes de tamanhos variados.

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] &

Uso

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

Explicação

Usando o primeiro exemplo de cima,

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

MapIndexeddefine índices para todos os elementos. NB: O Mathematica começa a contar com 1. (Mais tarde, levaremos isso em conta.)

MapIndexed[l, a, {2}]

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

Outergera todas as listas, cada uma candidata como uma matriz sanduíche, e os índices de seus elementos; %contém os resultados da saída anterior. Os números, 10e 22que destaquei após a saída, referem-se a uma matriz sanduíche {10,22}que ainda não foi identificada como tal.

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

Casestesta cada elemento acima para determinar se uma relação LessEqual(menor ou igual) é válida. Os resultados mostrados abaixo são aqueles em que os sanduíches de matriz foram detectados. Mais uma vez, destaquei {10,22}na saída.

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

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

%%refere-se aos penúltimos resultados. :>, [RuleDelayed] retorna essas partes das instâncias de interesse, ou seja, os índices dos sanduíches da matriz.  -1corrige o fato de o Mathematica iniciar matrizes com 1 em vez de 0. 

Cases[%%, 

x_ /; LessEqual @@ x [[Todos, 1]] == Verdadeiro:> x [[Todos, 2, 2]] - 1]

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

Gridexibe os resultados em uma grade. A primeira linha 0 1significa que o elemento 0 da primeira sub-lista (ou seja, 10 ) e o elemento 1 da segunda sub-lista (ou seja 22 ) constituem a primeira matriz sanduíche encontrada.

Grid@%

0 1

1 1

GolfScript, 51 caracteres

~:A{,}%{*}*,{A{,.@.@/\@%}%\;}%{:k,,{.A=\k==}%.$=},`

Exemplo de entrada (em stdin):

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

Exemplo de saída (para 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]]

(Observe que a entrada deve ser fornecida sem vírgulas; caso contrário, o programa provavelmente travará.)

Acho que devo adicionar alguma explicação sobre como esse código funciona:

• ~:Aapenas avalia a entrada como código GolfScript e atribui o resultado (uma matriz de matrizes) a A. Ele também deixa uma cópia Ana pilha para a próxima etapa.

• {,}%substitui cada sub-matriz pelo seu comprimento e {*}*multiplica esses comprimentos juntos, fornecendo o número total de possíveis candidatos a sanduíche. Esse número é então convertido por ,em uma matriz com tantos números inteiros sucessivos começando em 0.

• {A{,.@.@/\@%}%\;}%converte cada número em um candidato sanduíche correspondente (ou seja, uma matriz de índices válidos em cada sub-matriz em A). Por exemplo, dada a entrada acima, 0seria mapeada para [0 0 0], 1para [1 0 0], 2para [2 0 0], 3para [3 0 0], 4para [0 1 0]e assim por diante. (Descobrir exatamente como o código realiza isso é deixado como um exercício para o leitor interessado.)

• {:k,,{.A=\k==}%.$=},filtra os candidatos a sanduíche mapeando cada um deles para os elementos correspondentes das sub-matrizes de A(para que, por exemplo [0 0 0], produza [1 2 4], [1 0 0]produza [5 2 4]e assim por diante, para a entrada acima), classificando a matriz resultante e comparando-a com uma cópia não classificada . Se forem iguais, a matriz já foi classificada e, portanto, o candidato é realmente um sanduíche.

• Finalmente, `apenas transforma a matriz filtrada de sanduíches em uma sequência de saída.

R - 89 caracteres

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

Onde

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

ou

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

Pitão, 149 141 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))]

O Python possui uma biblioteca de ferramentas úteis que pode gerar permutações. Isso apenas repete todas as permutações possíveis de índices válidos e verifica se eles atendem aos critérios.

Eu acho que posso fazer isso mais curto, ainda trabalhando nisso.

Edit: Agora, toda uma linha para a sua leitura (in) conveniência!

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()))

... ainda pensa, "enumerar" é uma palavra muito longa.

GolfScript (44 caracteres)

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

O mesmo formato de entrada e saída da entrada de Ilmari.

Demo

Repartição aproximada:

Mapeie cada linha de entrada em uma matriz de pares [value index]

{.,,]zip}%

Dobre um produto cartesiano sobre as linhas

{{`{+}+1$\/}%\;}*

Filtre para aqueles cujas entradas 0, 2, 4, etc. não são decrescentes.

{2%.$=},

Mapeie cada um deles até as entradas 1, 3, 5, etc.

{(;2%}%

Q, 43

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