Größte deutlich summenfreie Partition

8

verwandt und inspiriert von - Finden von summenfreien Partitionen

Eine Menge Awird hier als eindeutig summenfrei definiert, wenn

  • 1) es besteht aus mindestens drei Elementen |A| ≥ 3, und
  • 2) seine unterschiedliche Selbstsumme A + A = { x + y | x, y in A}(mit x,yunterschiedlichen, dh x≠y) hat keine gemeinsamen Elemente mit A.

(Obsolete -... Sie diese nicht nach vorne gehen Sie dann Links hier nur , weil einige Antworten , die es verwendet haben es nicht mit den oben genannten Bedingungen entsprechen Alternativ kann die Gleichung x + y = zhat keine Lösung für x,y,z ∈ A(wieder mit x,y,zdeutlichen, das heißt x≠y, x≠z, y≠z.) )

Für ein einfaches Beispiel {1,3,5}ist es eindeutig summenfrei, ist es aber {1,3,4}nicht. {1,3}und {3}sind es auch nicht, da sie nicht mindestens drei Elemente sind.

Die Herausforderung besteht hier darin, die größte deutlich summenfreie Teilmenge der gegebenen Eingabe zu finden.

Eingang

  • Ein ungeordneter Satz Avon Ganzzahlen in einem beliebigen geeigneten Format .
  • Die Ganzzahlen können positiv, negativ oder null sein, es kann jedoch davon ausgegangen werden, dass sie in den nativen [int]Datentyp (oder einen gleichwertigen) Ihrer Sprache passen .
  • Das Set enthält garantiert nur unterschiedliche Elemente (hier keine Multisets).
  • Das Set ist nicht unbedingt sortiert.

Ausgabe

  • Die größte Teilmenge von A(die Aselbst sein könnte) ist eindeutig summenfrei. Die Ausgabe kann in jedem geeigneten Format erfolgen.
  • Wenn keine solche Teilmenge vorhanden ist, geben Sie eine leere Menge oder einen anderen False-Wert aus .
  • Wenn mehrere Teilmengen für die größte gebunden sind, geben Sie eine oder alle aus.
  • Die Teilmenge muss nicht unbedingt sortiert sein oder in derselben Reihenfolge wie die Eingabe. Zum Beispiel ist für die Eingabe die {1,3,5}Ausgabe {5,1,3}akzeptabel.

Zusätzliche Regeln

  • Standardlücken sind verboten.
  • Dies ist , daher gelten alle üblichen Golfregeln und der kürzeste Code gewinnt.

Beispiele

Input     -> Output (any or all)
{0}       -> {}
{1, 2, 3} -> {}
{1, 3, 5} -> {1, 3, 5}
{1, 2, 3, 4, 5} -> {1, 2, 5}  {1, 2, 4}  {1, 3, 5}  {2, 3, 4}  {2, 4, 5}  {3, 4, 5}
{-5, 4, 3, -2, 0} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-5, 4, 3, -2} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-17, 22, -5, 13, 200, -1, 1, 9} -> {-17, 22, -5, 13, 200, -1, 1}  {-17, 22, -5, 200, -1, 1, 9}  {-17, -5, 13, 200, -1, 1, 9}
AdmBorkBork
quelle

Antworten:

4

MATL , 47 43 Bytes

nW:qB!ts2#Sw2>)PZ)"1G@)XJ2XN!"@sJ@X-m~*]?J.

Probieren Sie es online aus!

Erläuterung

Dabei werden zwei Schleifen verwendet: eine äußere Schleife zum Generieren aller möglichen Teilmengen und eine innere Schleife zum Aufnehmen aller Elementpaare, um festzustellen, ob die Summe einem anderen Element der Teilmenge entspricht.

Teilmengen von mindestens 3 Elementen werden in der Reihenfolge abnehmender Anzahl von Elementen getestet. Der Code stoppt, sobald eine gültige Teilmenge gefunden wurde.

          % Take input implicitly
nW:q      % Generate [0 1 ... 2^n-1] where n is input length
B!        % Convert to binary. Gives a matrix. Each number corresponds to a column.
          % This will be used to select the elements of each subset
ts        % Duplicate. Sum of each column
2#S       % Sort. Output the sorted array and the indices of the sorting. Each index
          % corresponds to one possible subset
w2>       % Swap. Logical index of values that exceed 2. This is used to pick only
          % subsets of more than 2 elements
)         % Keeps only indices of subsets that have at least 3 elements
P         % Flip. This moves subsets with more elements to the front. As soon as a
          % subset fulfills the condition the outer loop will be exited, so we need
          % to start with the bigger subsets
Z)        % Index into columns of binary matrix. Each column is the binary pattern
          % defining a subset with at least 3 elements, starting with bigger subsets
"         % For each column. Each iteration corresponds to a subset
  1       %   Push 1
  G@)     %   Pick actual elements of each subset (logical index into input)
  XJ      %   Copy to clipboard J
  2XN!    %   All pairs of 2 elements from that subset. Each pair is a column
  "       %   For each column. Each iteration corresponds to a pair of elements
    @s    %     Sum of those two elements
    J@X-  %     Array with the other elements (obtained with set difference)
    m~    %     True if the sum of the two elemens is not a member of the array
    *     %     Multiply. Corresponds to logical AND
  ]       %   End for
  ?       %   If result is true: no sum of two elements equalled any element
    J     %     Push found subset (will be displayed implicitly)
    .     %     Exit loop
          %   End if implicitly
          % End for implicitly
          % Display stack implicitly
Luis Mendo
quelle
3

Python, 137 Bytes

Ein naiver Ansatz. Durchläuft alle Teilmengen der Eingabe, die mindestens 3 Werte enthalten, und überprüft die Eigenschaften für jeden einzelnen. Gibt zurück, []wenn kein Ergebnis gefunden wird oder [S]wenn mindestens ein Ergebnis gefunden wird (wo Ssich ein Tupel befindet).

from itertools import*
lambda a:[c for n in range(3,len(a)+1)for c in combinations(a,n)if all(x+y-z for(x,y,z)in permutations(c,3))][-1:]
Lynn
quelle
2

Javascript 246 263

a=>([...Array(1<<(l=a.length))].map((x,i)=>i.toString(2)).filter(n=>/1.*1.*1/.test(n)).map(s=>('0'.repeat(l)+s).slice(-l).replace(/./g,(b,p)=>+b&&o.push(a[p]),o=[])&&o).filter(u=>u.every((x,i)=>!u.some((y,j)=>j-i&&u.some((z,k)=>k-j&&!(z-x-y))))))

So lange :( ... Aber es war eine schöne Codierung .. (glaube ich)

Weniger Golf:

f=a=>(
    [...Array(1<<(l=a.length))]
        .map((x,i)=>i.toString(2))
        .filter(n=>/1.*1.*1/.test(n))
        .map(s=>
            ('0'.repeat(l)+s).slice(-l).replace(/./g,
                (b,p)=>+b&&o.push(a[p])
            ,o=[])&&o
        )
        .filter(u=>
            u.every((x,i)=>
                !u.some((y,j)=>
                    j-i&&u.some((z,k)=>k-j&&!(z-x-y))
                )
            )
        )
)

document.body.innerHTML = JSON.stringify( f([1,2,3,4,5]), null, 1 );

Washington Guedes
quelle
2

Mathematica - 89 84 83 77 76 Bytes

6 Bytes dank @ Sp3000 gespeichert

Kann wahrscheinlich viel mehr Golf gespielt werden, gibt es einen kürzeren Weg zum Filtern?

Select[Subsets@#,Length@#>2&&Intersection[#,Tr/@#~Subsets~{2}]=={}&]~Last~0&

Anonyme Funktion, gibt 0bei keiner Antwort zurück.

Maltysen
quelle
2

Ruby, 107 Bytes

Die Eingabe ist ein Array. Sammelt eine qualifizierende Teilmenge für jede Teilmengengröße von 3bis zur Eingabelänge und gibt dann die größte der gefundenen zurück. Kehrt zurücknil wenn kein Ergebnis gefunden wird.

Aufgrund der widersprüchlichen Spezifikation gibt es zwei Lösungen, die derzeit dieselbe Bytezahl haben.

Mit der ersten Definition: ( { x + y | x, y ∈ A } ∩ A = ∅)

->s{((3..s.size).map{|i|s.combination(i).find{|e|e.combination(2).map{|a,b|a+b}&e==[]}}-[p])[-1]}

Verwendung der zweiten Definition ( ∀ x, y, z ∈ A: x + y ≠ z)

->s{((3..s.size).map{|i|s.combination(i).find{|e|e.permutation(3).all?{|a,b,c|a+b!=c}}}-[p])[-1]}
Wert Tinte
quelle
0

Pyth, 27 Bytes

ef!f!*Fm-Fd.pYfqlY3yTfglT3y

Testsuite.

Undichte Nonne
quelle
Wie funktioniert das? Ich scheine unerwartete Ausgabe zu bekommen, wenn ich es auf TIO laufen lasse.
AdmBorkBork
Entschuldigung, jetzt behoben.
Undichte Nonne
1
Funktioniert nicht für die Eingabe 1,3,5,100, da auch die Teilmenge gedruckt 1,3,5wird, die nicht maximal ist.
Jakube
1
@ Jakube Lassen Sie die Initiale fallen eund posten Sie dann als separate Lösung: D
Leaky Nun
1
Wir müssen die größte Teilmenge oder alle größten Teilmengen drucken. Das eist also erforderlich.
Jakube