Máximas subsecuencias sumadas con elementos no adyacentes

23

Introducción:

Inspirado por estas dos preguntas SO (sin duda de la misma clase): imprima los elementos en la submatriz de suma máxima sin elementos adyacentes java y la suma máxima de elementos no adyacentes de una matriz, para imprimir .

Reto:

Dada una lista de enteros, genera una subsecuencia que consiste en elementos no adyacentes que tienen la suma más alta. Aquí algunos ejemplos:

  • [1,2,3,-1,-3,2,5]daría como resultado [1,3,5](con una suma de 9) en los índices basados ​​en 0 [0,2,6].
  • [4,5,4,3]daría como resultado [4,4](con una suma de 8) en los índices basados ​​en 0 [0,2]o [5,3](también con una suma de 8) en los índices basados ​​en 0 [1,3].
  • [5,5,10,100,10,5]daría como resultado [5,100,5](con una suma de 110) en los índices basados ​​en 0 [0,3,5]o [1,3,5].

Lo que es más importante sobre estos ejemplos anteriores, los índices que contienen los elementos están al menos 2 separados entre sí. Si miramos el ejemplo [5,5,10,100,10,5]más en profundidad: tenemos la siguiente subsecuencia potencial que contiene elementos no adyacentes; con sus índices debajo de él; con sus sumas debajo de eso:

[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]]   // non-adjacent subsequences
[[5],[ 4],[  3],[ 2],[1],[0],[  3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1,  3],[0,5],[0, 4],[0,  3],[0, 2],[1,  3,5],[0,  3,5],[0, 2,5],[0, 2, 4]]   // at these 0-based indices
[  5,  10,  100,  10,  5,  5,    105,    15,     20,   10,    15,    105,   10,    15,    105,    15,      110,      110,      20,       25]   // with these sums
                                                                                                            ^         ^                        // and these two maximums

Dado que las sumas máximas son 110, generamos [5,100,5]resultados

Reglas de desafío:

  • Se le permite generar pares clave-valor del índice + valor. Entonces, en lugar de [5,100,5]usted, puede generar resultados [[0,5],[3,100],[5,5]]o [[1,5],[3,100],[5,5]]como resultado (o [[1,5],[4,100],[6,5]]/ [[2,5],[4,100],[6,5]]cuando se utiliza la indexación basada en 1 en lugar de la basada en 0).
    • Si usa pares clave-valor, también pueden estar en orden inverso o aleatorio, ya que está claro qué valores se deben al índice emparejado.
    • No se permite generar solo los índices sin valores. Debería generar los valores o los valores / índices como pares clave-valor (o dos listas separadas para 'claves' y 'valores' del mismo tamaño si los pares clave-valor no son posibles en el idioma que elija).
  • Se le permite generar todas las subsecuencias posibles con la suma máxima en lugar de solo una.
  • Como puede ver en los ejemplos, la lista de entrada también puede contener valores negativos y duplicados. Puede suponer que los enteros de entrada están dentro del rango [−999,999] .
  • La lista de salida no puede estar vacía y siempre debe contener al menos un elemento (si una lista solo contendría valores negativos, una lista que contenga el único valor negativo más bajo se generaría como resultado; consulte los últimos dos casos de prueba).
  • Si hay una salida posible pero para múltiples índices diferentes, se permite la salida de ambos aunque parezcan duplicados. (es decir, el ejemplo anterior, puede generar [[5,100,5],[5,100,5]]ambas combinaciones de índices posibles).

Casos de prueba:

Input:                   Possible outputs:       At 0-based indices:     With sum:

[1,2,3,-1,-3,2,5]        [1,3,5]                 [0,2,6]                 9
[4,5,4,3]                [4,4]/[5,3]             [0,2]/[1,3]             8
[5,5,10,100,10,5]        [5,100,5]               [0,3,5]/[1,3,5]         110
[10]                     [10]                    [0]                     10
[1,1,1]                  [1,1]                   [0,2]                   2
[-3,7,4,-2,4]            [7,4]                   [1,4]                   11
[1,7,4,-2]               [7]                     [1]                     7
[1,2,-3,-4,5,6,-7]       [2,6]                   [1,5]                   8
[800,-31,0,0,421,726]    [800,726]/[800,0,726]   [0,5]/[0,3,5]/[0,2,5]   1526
[-1,7,8,-5,40,40]        [8,40]                  [2,4]/[2,5]             48
[-5,-18,-3,-1,-10]       [-1]                    [3]                     -1
[0,-3,-41,0,-99,-2,0]    [0]/[0,0]/[0,0,0]       [0]/[3]/[6]/[0,3]/
                                                  [0,6],[3,6]/[0,3,6]    0
code-golf number array-manipulation integer Kevin Cruijssen
fuente
Si hay más de un conjunto idéntico (pero de diferentes índices), ¿está bien enumerarlos todos? Por ejemplo, [5,100,5]dos veces para su tercer ejemplo.
Nick Kennedy
1
powersetes un conjunto de subconjuntos, ¿no? pero parece que estás devolviendo un conjunto de subsecuencias? [4,5,4,3] daría como resultado [4,4] donde [4,4] claramente no es un conjunto.
Datos
1
@Arnauld Sí, si los valores son pares clave-valor con su índice, está claro qué valores indexados se entienden en la entrada, por lo que pueden estar en cualquier orden. También editará esto en la descripción del desafío.
Kevin Cruijssen
2
Solo para estar seguro: generar los índices no es una opción, ¿verdad?
Shaggy
1
El término clásico es "subsecuencia" . Sin embargo, esto tiene el mismo problema de las personas que piensan en subsecuencias contiguas. Yo diría "subconjunto" si realmente estuviéramos trabajando con conjuntos aquí, pero estas son definitivamente secuencias: el orden importa y los duplicados están permitidos.
user2357112 es compatible con Monica el

Respuestas:

6

Casco , 11 bytes

►Σ†!¹mü≈tṖŀ

Pruébalo en línea!

Explicación

►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
          ŀ  Indices: [1,2,3,4]
         Ṗ   Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
        t    Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
     m       For each,
      ü      de-duplicate by
       ≈     differing by at most 1.
             For example, [1,2,4] becomes [1,4].
  †          Deep map
   !¹        indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
►            Maximum by
 Σ           sum: [5,4]
Zgarb
fuente
6

Haskell , 60 bytes

snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)

Pruébalo en línea!

La función auxiliar se %bifurca recursivamente al elegir si incluir el primer elemento y soltar el segundo, o saltear el primer elemento. Toma el máximo de todos los resultados, que son tuplas cuyo primer elemento es la suma y cuyo segundo elemento es la lista correspondiente que se extrae para la salida.

Para manejar la regla de que la lista vacía está prohibida, incluso si tuviera el truco más pequeño, hacemos un lindo truco de escritura en sum r<$rlugar de sum r. Esto hace una lista cuyos elementos son todos sum ry cuya longitud es la de r. De esa manera, cuando elegimos el máximo, priorizamos cualquier lista sobre un vacío r, pero de lo contrario las comparaciones dependen del primer elemento que sea sum r.

xnor
fuente
6

R , 136125 bytes

function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]

Pruébalo en línea!

-6 bytes gracias a digEmAll , que por cierto también me superó .

Devuelve la subsecuencia más corta como a list, rompiendo vínculos en lexicografía primero por índices.

La fuerza bruta genera todas las subsecuencias de índice, luego Filters para aquellas que no son adyacentes, es decir, dónde all(diff(x)>1). Luego subconjuntos [en el luso de estos índices, seleccionando [[el primero donde la suma es el máximo ( which.max).

¡Estoy bastante seguro de que esta es la primera respuesta R que he escrito que utiliza Filter! triste, Filteres infiel, no es de extrañar que nunca lo haya usado ...

Giuseppe
fuente
130
digEmAll
@digEmAll gracias!
Giuseppe
5

05AB1E , 14 bytes

Guardado 1 byte gracias a Kevin Cruijssen

ā<æʒĆ¥≠W}èΣO}θ

Pruébalo en línea! o como un conjunto de pruebas

Explicación

ā<               # push [0 ... len(input)-1]
  æ              # compute powerset
   ʒ    }        # filter, keep lists where:
      ≠W         # no element is 1 in the
     ¥           # deltas
    Ć            # of the list with the head appended
         è       # index into the input with each
          ΣO}    # sort by sum
             θ   # take the last element
Emigna
fuente
Puede que no estés contento, pero aún es 4 bytes más corto que mi solución inicial. ;) Y puedes jugar al golf 1 más cambiando ¤ªa Ć.
Kevin Cruijssen
@KevinCruijssen: ¡Oh, sí! Por alguna razón me convencí de que necesitaba un elemento repetido al final. ¡Gracias!
Emigna
5

Brachylog (v2), 14 bytes

{~ba~c∋₁ᵐ}ᶠ+ᵒt

Pruébalo en línea!

Presentación de funciones; entrada desde la izquierda, salida desde la derecha, como de costumbre. Muy lento; Una lista de cinco elementos es probablemente el máximo para probar en TIO.

{~ba~c∋₁ᵐ}ᶠ+ᵒt
 ~b              Prepend an arbitrary element to the input
   a             Take a prefix or suffix of the resulting list
    ~c           Ordered partition into contiguous sublists
      ∋₁         Take the second element
        ᵐ          of each sublist
{        }ᶠ      Find all possible ways to do this
           +ᵒ    Sort by sum
             t   Take the greatest

Los resultados que obtenemos de los prefijos no son incorrectos, pero tampoco son interesantes; todos los resultados posibles se generan tomando un sufijo (que posiblemente sea la lista en sí, pero no puede estar vacío), pero "sufijo" es más detallado en Brachylog que "prefijo o sufijo", así que elegí la versión que es más terser (y menos eficiente pero aún correcto). La idea básica es que para cada elemento que queremos en la lista de salida, la partición en sublistas contiguas necesita colocar ese elemento y el elemento antes en la misma sublista (porque el elemento es el segundoelemento de la sublista), por lo que no pueden aparecer dos elementos consecutivos en el resultado. Por otro lado, está bastante claro que cualquier lista sin dos elementos consecutivos puede aparecer en el resultado. Entonces, una vez que tengamos todas las listas de candidatos posibles, podemos tomar las sumas de todas y ver cuál es la más grande.

ais523
fuente
3

JavaScript (ES6),  138 132 130 129  126 bytes

Salidas pares clave-valor.

a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r

Pruébalo en línea!

Paso 1

[vunaltumi,yonorteremiX]

a.reduce((a, x, i) => // for each value x at position i:
  [                   //   update a[] to a new array consisting of:
    ...a,             //     all previous entries
    ...a.map(y =>     //     for each value y in a[]:
      [[x, i], ...y]  //       append [x, i], followed by all original entries
    )                 //     end of map()
  ],                  //   end of new array
  [[]]                //   start with a = [[]]
)                     // end of reduce()

Paso 2

metror

.map(m =              // initialize m to a non-numeric value
  a =>                // for each entry a[] in the powerset:
  a.some(s = p =      //   initialize s and p to non numeric values
    ([v, i]) =>       //   for each value v and each index i in a[]:
    p - (             //     compute p - i
      s = ~~s + v,    //     add v to s
      p = i           //     update p to i
    ) < 2             //     if p - i is less than 2, yield true
  ) |                 //   end of some()
  s < m ||            //   unless some() was truthy or s is less than m,
  (r = a, m = s)      //   save a[] in r[] and update m to s
) && r                // end of map(); return r[]
Arnauld
fuente
3

Haskell, 81 80 bytes

snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a

Pruébalo en línea!

fconstruye todas las subsecuencias válidas omitiendo el siguiente elemento ( f(b:c)) o usándolo y omitiendo el siguiente ( map(a:)(f c)) y trabaja recursivamente en el resto. Para el resultado, construya todas las subsecuencias ( f), suelte la subsecuencia vacía (que aparece primero en la lista:) tail, haga pares (<sum>,<subsequence>)( map((,)=<<sum)), encuentre el máximo (los pares se comparan en orden lexicográfico) -> maximum) y suelte la suma ( snd).

Editar: -1 byte gracias a @Lynn.

nimi
fuente
1
map(:[])aes un byte más corto que (pure<$>a)^^
Lynn
3

T-SQL, 122 119 118 bytes

La entrada es una variable de tabla.

Esta consulta selecciona todos los elementos de la variable de tabla, combinándolos con todos los elementos no adyacentes con valores de posición más altos y muestra el texto generado para la suma más alta de estos valores.

WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON~-i>j)SELECT
TOP 1y FROM C ORDER BY-v

Pruébelo en línea sin golf

t-clausen.dk
fuente
2

Pyth, 19 bytes

esDm@LQdtf!q#1.+TyU

Pruébelo en línea aquí , o verifique todos los casos de prueba a la vez aquí .

esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
                       Trailing Q inferred
                  UQ   Generate range [0-len(Q))
                 y     Take the powerset of the above
         f             Filter keep elements of the above, as T, using:
              .+T        Take differences of consecutive elements of T
           q#1           Keep those differences equal to 1
          !              Logical NOT - empty lists evaluate to true, populated ones to false
                       Result of the filter is those sets without consecutive numbers
        t              Drop the first element (empty set)
   m                   Map the remaining sets, as d, using:
     L d                 For each element of d...
    @ Q                  ... get the element in Q with that index
 sD                    Order the sets by their sum
e                      Take the last element, implicit print
Sok
fuente
2

Gaia , 24 bytes

e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠

Pruébalo en línea!

Uf, E‡hace algunas cosas raras ... de acuerdo a la documentación, se debe hacer algo como "longitud dada iconjunto de listas Xy longitud jconjunto de índices Y, el regreso X[i][Y[j]]", sino que se devuelve [X[i][Y[j]] X[i][Y[-j]]en la indexación negativo representa el complemento, por lo que tenemos que hacer ev2%para extraer solo los que queramos.

e				| eval as a list l
 :				| dup
  w				| wrap as a list
   ;				| push l again
    ċ				| push [1..len(l)]
     z				| push all subsets of [1..len(l)] -- index powerset.
      ⟨      ⟩⁇			| filter this for:
       ọ			| deltas
        1>¦			| are greater than 1
           ẏ			| all (all deltas greater than 1)
	       ‼⁇		| filter for non-empty lists
		 E‡		| table extract elements. Given l and index set i, this pushes
				| [l[i] l[setdiff(1..l,i)]] for some reason
		   ev2%		| get the l[i] only by unlisting, reversing, and taking every other element
		       Σ⌠	| Get the one with the maximum sum
Giuseppe
fuente
Por curiosidad, ¿por qué la salida tiene dos finales en ]]lugar de uno?
Kevin Cruijssen
@KevinCruijssen Solo otra peculiaridad divertida del intérprete; todas las listas se imprimen así, por lo que [[1] [2]]se imprime , lo [[1]] [2]]]]que hace que sea muy difícil leer / depurar la salida de la lista.
Giuseppe
Yo creo que es debido a la expresión re.sub(" ?$","]",result)en el intérprete que en su lugar debería ser re.sub(" +$","]",result), pero mi pitón es muy mala.
Giuseppe
2

R , 108 107 bytes

function(v,M=-Inf){for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M}

Pruébalo en línea!

-1 gracias a @Giuseppe

digEmAll
fuente
2

Wolfram Language (Mathematica) , 70 63 bytes

MaximalBy[Select[q=Rest@Subsets@#,!FreeQ[q,#~Riffle~_]&],Tr,1]&

Pruébalo en línea!

Búsqueda de alto nivel

          Select[q=Rest@Subsets@#,                     ]        (*choose nonempty subsets of the input such that*)
                                  !FreeQ[q,          ]&         (*there exists a subset of the input which matches*)
                                           #~Riffle~_           (*this list, with an item inserted between adjacent elements*)
MaximalBy[                                              ,Tr,1]& (*and return one with the greatest total*)

,1es necesario para no devolver involuntariamente conjuntos no válidos (de lo contrario, por ejemplo, una entrada de {1,1,1}daría como resultado una salida de {{1,1},{1,1},{1,1}})

attinat
fuente
1

Haskell , 300 168 bytes

import Data.List
h[]=1>2
h(x:y)=fst$foldl(\a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]

Pruébalo en línea!

-132 bytes gracias a todos los comentarios de @nimi :)

Original

Sin golf (original)

import Data.List
import Data.Function

f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]

g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs

h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (\acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter (\(elements, indices) -> h indices) xs

k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map (\(elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs

z -- put things together
```
loco
fuente
1
Algunos consejos: voltee el elemento y su índice dentro de los pares devueltos por f:, f x=zip[0..length x]xentonces se fconvierte f=zip[0..]. ges justo g=map unzip. La función para filtrar jes h.fst(<- ¡pares invertidos!). j=filter(h.fst). El foldl1+from kes sumy con un par de puntos libres k=map((,)=<<sum.snd). sortBy(...)puede ser sustituido por sortOn fst: l=snd.last.sortOn fst. Finalmente, ya que está utilizando todas las funciones solo una vez, puede incorporarlas en una única expresión sin puntos:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
nimi
.... Pruébalo en línea! .
nimi
Ah, y ya no es necesario importar Data.Function.
nimi
Eso es genial, gracias por los comentarios :)
errores
A continuación h: buscamos elementos no adyacentes, es decir, la diferencia de los índices adyacentes debe ser >1. zipWith(-)=<<tailconstruye una lista de tales diferencias, pero falla para la lista vacía, por lo que necesitamos un adicional tailen el subsequencesque deshacerse de él. En línea de nuevo. Pruébalo en línea!
nimi
1

Carbón , 46 bytes

≔⟦υ⟧ηＦθ«≔υζ≔Ｅη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔ＥηΣιζＩ§η⌕ζ⌈ζ

Pruébalo en línea!El enlace es a la versión detallada del código. Explicación:

≔⟦υ⟧η

La variable uestá predefinida con una lista vacía. Esto se pone en una lista que se asigna a h. Estas variables actúan como acumuladores.ucontiene las sublistas que incluyen el último elemento de la entrada, qmientras que hcontiene las sublistas que no lo hacen (y, por lo tanto, son adecuadas para agregar el siguiente elemento de la entrada).

Ｆθ«

Recorre los elementos de la entrada.

≔υζ

Guarde la lista de sublistas que contienen el elemento anterior.

≔Ｅη⁺κ⟦ι⟧υ

Tome todas las sublistas que no contengan el elemento anterior, agregue el elemento actual y guarde el resultado como la lista de sublistas que contienen el elemento actual. (No usoPush aquí, ya que necesito clonar la lista).

≔⁺ζηη»

Concatene ambas sublistas anteriores en la nueva lista de sublistas que no contienen el elemento actual.

≔Φ⁺υηιη

Concatene las sublistas por última vez y elimine la lista vacía original (que el carbón no puede sumar de todos modos).

≔ＥηΣιζ

Calcule las sumas de todas las sublistas.

Ｉ§η⌕ζ⌈ζ

Encuentre un índice de la mayor suma y genere la sublista correspondiente.

Neil
fuente
1

Japt -h , 21 bytes

¿Alguna vez has tenido uno de esos desafíos donde olvidas por completo cómo jugar golf?

ð¤à fÊk_än ø1îmgUÃñx

Intentalo

ð¤à fÊk_än ø1îmgUÃñx     :Implicit input of array U
ð                         :Indices of elements that return true when
 ¤                        :  Converted to a base-2 string (to account for 0s)
  à                       :Combinations
    f                     :Filter by
     Ê                    :  Length (to remove the empty combination)
      k_                  :Remove elements that return true
        än                :  Deltas
           ø1             :  Contains 1
             Ã            :End remove
              ®           :Map
               m          :  Map
                gU        :    Index into U
                  Ã       :End map
                   ñ      :Sort by
                    x     :  Sum
                          :Implicit output of last element
Lanudo
fuente
1

Python 2 , 63 70 65 bytes

f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a

Pruébalo en línea!

5 bytes thx a ArBo

Chas Brown
fuente
Su caso de prueba [1, 7, 4, -2] [1, 4] 5 7está obteniendo la respuesta incorrecta.
xnor
@xnor: arreglado ahora.
Chas Brown
65 bytes
ArBo