Finden Sie die maximale Übereinstimmung in der Teilbarkeitsrelation

16

Sie erhalten eine Reihe von positiven ganzen Zahlen. Sie müssen sie paarweise so anordnen, dass:

  • Jedes Paar enthält 2 Zahlen, von denen eine ein Vielfaches einer anderen ist. Beispielsweise ist 8 ein Vielfaches von 4 und 9 ein Vielfaches von 9.
  • Wenn die gleiche Zahl im Anfangssatz mehrmals vorkommt, kann sie in den Paaren so oft verwendet werden. Eine Nummer kann sogar mit einem anderen Vorkommen derselben Nummer gepaart werden
  • Die maximal mögliche Anzahl von Paaren wird erhalten.

Die Ausgabe muss die Anzahl der Paare sein. Kürzester Code gewinnt.

Beispieldaten

2,3,4,8,9,18 -> 3

7,14,28,42,56 -> 2

7,1,9,9,4,9,9,1,3,9,8,5 -> 6

8,88,888,8888,88888,888888 -> 3

2,6,7,17,16,35,15,9,83,7 -> 2

ghosts_in_the_code
quelle
3
Weiß jemand, ob dieses Problem NP-vollständig ist? Ich denke der kleinste "harte" Satz ist 2,3,4,8,9,18. (Jede Zahl in dieser Liste ist ein Faktor und / oder ein Vielfaches von mindestens zwei anderen Zahlen in der Liste, aber es gibt nur eine Lösung.)
Neil

Antworten:

6

Haskell, 109 107 76 70 Bytes

Vielen Dank an nimi, der 33 Bytes gespart und mir etwas mehr Haskell beigebracht hat. :)
Danke an xnor für das Speichern weiterer 6 Bytes.

import Data.List
f l=maximum$0:[1+f t|a:b:t<-permutations l,a`mod`b<1]

Ja, mein erster Haskell Golf. Es funktioniert genauso wie alle bisherigen Antworten (na ja, nicht ganz: Es zählt nur die Länge des längsten Präfixes von gültigen Paaren in jeder Permutation, aber das ist äquivalent und entspricht tatsächlich dem, was mein ursprünglicher CJam-Code getan hat).

Für mehr Golf ist es auch ineffizient, indem alle Permutationen des Suffix jedes Mal rekursiv generiert werden, wenn die ersten beiden Elemente einer Permutation ein gültiges Paar sind.

Martin Ender
quelle
Ist das f=nötig?
Alex A.
@AlexA. Ich bin nicht sicher, wie die Standardrichtlinie für PPCG für unbenannte Funktionen in Haskell lautet, aber ich habe einige andere Haskell-Antworten überprüft und sie haben benannte Funktionen verwendet. Außerdem müssten Sie technisch gesehen Klammern um die Funktion verwenden, wenn Sie sie als unbenannte Funktion verwenden möchten, damit die Anzahl der Bytes sowieso gleich ist, denke ich.
Martin Ender
@nimi Danke, dass du mich informiert hast. :) Sehen Sie noch etwas, das gekürzt werden könnte? Der Import für chunksOfist schmerzhaft. Ich kenne die Standardbibliothek von Haskell nicht wirklich, um feststellen zu können, ob es eine kürzere äquivalente Funktion gibt. Ich habe versucht, es selbst zu implementieren, aber es kam zwei oder drei Bytes länger als der Import heraus.
Martin Ender
ohhh, beides zu fangen []und [_]gleichzeitig den g x=[]zweiten Platz zu belegen, ist wirklich klug. Ich werde es versuchen. Danke :)
Martin Ender
Sieht ein bisschen kürzer die ganze Funktion zu definieren rekursiv: f l=maximum$0:[1+f t|(a:b:t)<-permutations l,a`mod`b<1].
26.
3

CJam, 22 18 Bytes

q~e!{2/::%0e=}%:e>

Probieren Sie es online aus.

Erwartet Eingaben in Form einer CJam-Liste.

Dies ist für größere Listen ein wenig ineffizient (und Java wird wahrscheinlich keinen Speicher mehr haben, wenn Sie nicht mehr angeben).

Erläuterung

q~     e# Read and evaluate input.
e!     e# Get all distinct permutations.
{      e# Map this block onto each permutation...
  2/   e#   Split the list into (consecutive) pairs. There may be a single element at the
       e#   end, which doesn't participate in any pair.
  ::%  e#   Fold modulo onto each chunk. If it's a pair, this computes the modulo, which
       e#   yields 0 if the first element is a multiple of the second. If the list has only
       e#   one element, it will simply return that element, which we know is positive.
  0e=  e#   Count the number of zeroes (valid pairs).
}%
:e>    e# Find the maximum of the list by folding max() onto it.
Martin Ender
quelle
Es gibt keine Ausgabe für [1 2 3 4 5 6 7 8 9 10]Jedoch, [7 1 9 9 4 9 9 1 3 9 8 1]die eine längere Liste ist, funktioniert ordnungsgemäß. Warum das?
ghosts_in_the_code
@ghosts_in_the_code Weil ersteres deutlichere Permutationen hat. 10! = 3628800, aber 12! / 5! / 3! = 665280. Für den ersten Fall ist also kein Speicher mehr verfügbar. Wenn Sie es über die Konsole mit dem Java-Interpreter ausführen, könnten Sie Java anweisen, mehr Speicher zu verwenden, und der erste Fall würde ebenfalls funktionieren (obwohl es eine Weile dauern könnte, weiß nicht).
Martin Ender
3

Pyth, 13 Bytes

eSm/%Mcd2Z.pQ

Der Zeit- und Speicheraufwand ist wirklich schrecklich. Als erstes erstelle ich eine Liste mit allen Permutationen der ursprünglichen Liste. Dies nimmt n*n!Speicherplatz in Anspruch. Eingabelisten mit der Länge 9 dauern schon ziemlich lange.

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung:

eSm/%Mcd2Z.pQ
            Q   read the list of integer
          .p    create the list of all permutations
  m             map each permutation d to:
      cd2          split d into lists of length 2
    %M             apply modulo to each of this lists
   /     Z         count the zeros (=number of pairs with the first 
                   item divisible by the second)
 S              sort these values
e               and print the last one (=maximum)
Jakube
quelle
2

Mathematica, 95 93 87 83 79 60 58 Bytes

Max[Count[#~Partition~2,{a_,b_}/;a∣b]&/@Permutations@#]&

Dauert einige Sekunden für die größeren Beispiele.

LegionMammal978
quelle
0

Matlab (120 + 114 = 234)

  function w=t(y,z),w=0;for i=1:size(z,1),w=max(w,1+t([y,z(i,:)],feval(@(d)z(d(:,1)&d(:,2),:),~ismember(z,z(i,:)))));end

Main:

  a=input('');h=bsxfun(@mod,a,a');v=[];for i=1:size(h,1) b=find(~h(i,:));v=[v;[(2:nnz(b))*0+i;b(b~=i)]'];end;t([],v)

  • Die Topper-Funktion wird vom Hauptteil aufgerufen.

  • Die Eingabe erfolgt im Formular [. . .]

Abr001am
quelle
0

Matlab (365)

  j=@(e,x)['b(:,' num2str(e(x)) ')'];r=@(e,y)arrayfun(@(t)['((mod(' j(e,1) ',' j(e,t) ')==0|mod(' j(e,t) ',' j(e,1) ')==0)&',(y<4)*49,[cell2mat(strcat(r(e(setdiff(2:y,t)),y-2),'|')) '0'],')'],2:y,'UniformOutput',0);a=input('');i=nnz(a);i=i-mod(i,2);q=0;while(~q)b=nchoosek(a,i);q=[cell2mat(strcat((r(1:i,i)),'|')) '0'];q=nnz(b(eval(q(q~=0)),:));i=i-2;end;fix((i+2)/2)

  • Das ist anscheinend länger, aber Oneliner und Executive, und ich habe es geschafft, der permsFunktion zu entkommen , weil es ewig dauert.

  • Diese Funktion braucht viele Wiederholungen, um aufgrund anonymer Funktionen ruhig zu laufen, ich bin offen für Vorschläge hier :)

Abr001am
quelle