Найти максимальное совпадение в отношении делимости

16

Вам дан набор натуральных чисел. Вы должны расположить их в пары так, чтобы:

  • Каждая пара содержит 2 числа, одно из которых кратно другому. Например, 8 кратно 4, а 9 кратно 9.
  • Если одно и то же число встречается много раз в исходном наборе, его можно использовать много раз в парах; число может даже быть соединено с другим вхождением того же самого числа
  • Максимально возможное количество пар получается.

На выходе должно быть количество пар. Самый короткий код выигрывает.

Образец данных

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
источник
3
Кто-нибудь знает, является ли эта проблема NP-полной? Я думаю, что самый маленький "жесткий" набор 2,3,4,8,9,18. (Каждое число в этом списке является фактором и / или кратным как минимум двум другим числам в списке, но у него есть только одно решение.)
Нейл

Ответы:

6

Haskell, 109 107 76 70 байт

Спасибо Ними за то, что он сэкономил 33 байта и научил меня еще немного на Haskell. :)
Спасибо xnor за сохранение еще 6 байтов.

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

Yay, мой первый гольф на Haskell. Он работает так же, как и все ответы на данный момент (ну, не совсем: он учитывает только длину самого длинного префикса допустимых пар в каждой перестановке, но это эквивалентно и фактически соответствует тому, что сделал мой оригинальный код CJam).

Для дополнительной гольфивности это также крайне неэффективно за счет рекурсивного генерирования всех перестановок суффикса каждый раз, когда первые два элемента перестановки являются допустимой парой.

Мартин Эндер
источник
Это f=необходимо?
Алекс А.
@AlexA. Я не уверен, какова стандартная политика PPCG для неназванных функций в Haskell, но я проверил несколько других ответов на Haskell, и они использовали именованные функции. Кроме того, технически вам придется использовать круглые скобки вокруг функции, если вы хотите использовать ее как безымянную функцию, так что в любом случае, я думаю, это будет то же число байтов.
Мартин Эндер
@nimi Спасибо, что дали мне знать. :) Вы видите что-нибудь еще, что можно сократить? Импорт для chunksOfбольно. Я на самом деле не знаю стандартной библиотеки Haskell, чтобы можно было определить, существует ли более короткая эквивалентная функция. Я попытался реализовать это сам, но он получился на два или три байта длиннее, чем импорт.
Мартин Эндер,
оооо, ловить и то []и другое [_], поставив g x=[]секунду, действительно умно. Я попробую. Спасибо :)
Мартин Эндер
Выглядит немного короче , чтобы определить все функции рекурсивно: f l=maximum$0:[1+f t|(a:b:t)<-permutations l,a`mod`b<1].
xnor
3

CJam, 22 18 байт

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

Попробуйте онлайн.

Ожидается ввод в виде списка в стиле CJam.

Это немного неэффективно для больших списков (и Java, вероятно, исчерпает память, если вы не дадите ей больше).

объяснение

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.
Мартин Эндер
источник
Это не дает вывод для [1 2 3 4 5 6 7 8 9 10]Однако, [7 1 9 9 4 9 9 1 3 9 8 1]который является более длинным списком, работает должным образом. Это почему?
ghosts_in_the_code
@ghosts_in_the_code Потому что первый имеет более четкие перестановки. 10! = 3628800, но 12! / 5! / 3! = 665280. Так что для первого случая не хватает памяти. Если вы запускаете его из консоли с помощью интерпретатора Java, вы можете указать Java использовать больше памяти, и первый случай также будет работать (хотя это может занять некоторое время, не знаю).
Мартин Эндер
3

Pyth, 13 байт

eSm/%Mcd2Z.pQ

Время и сложность хранения действительно ужасны. Первое, что я делаю, это создаю список со всеми перестановками исходного списка. Это занимает n*n!хранение. Входные списки длиной 9 уже занимают довольно много времени.

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

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
источник
2

Mathematica, 95 93 87 83 79 60 58 байт

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

Занимает несколько секунд для более крупных примеров.

LegionMammal978
источник
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

основной:

  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)

  • функция topper вызывается основной частью.

  • вход находится в форме [. . .]

Abr001am
источник
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)

  • Это, видимо, дольше, но один и более исполнительный, и мне удалось избежать permsфункции, потому что это занимает вечность.

  • Эта функция требует много реприз, чтобы работать спокойно из-за анонимных функций, я открыт для предложений здесь :)

Abr001am
источник