Find maximal matching in divisibility relation

Question

You are given a set of positive integers. You must arrange them into pairs such that:

• Each pair contains 2 numbers, one of which is a multiple of another. For example, 8 is a multiple of 4, and 9 is a multiple of 9.
• If the same number occurs many times in the initial set, it can be used that many times in the pairs; a number can even be paired with another occurence of the same number
• The maximum possible number of pairs is obtained.

Output must be the number of pairs. Shortest code wins.

Sample data

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

Answer 1

Haskell, 109 107 76 70 bytes

Thanks to nimi for saving 33 bytes and teaching me some more Haskell. :)
Thanks to xnor for saving another 6 bytes.

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

Yay, my first Haskell golf. It works the same as all the answers so far (well, not quite: it only counts the length of the longest prefix of valid pairs in each permutation, but that's equivalent and is actually what my original CJam code did).

For extra golfitude it's also extra inefficient by recursively generating all permutations of the suffix each time the first two elements of a permutation are a valid pair.

Answer 2

CJam, 22 18 bytes

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

Try it online.

Expects input in the form of a CJam-style list.

This is a bit inefficient for larger lists (and Java will probably run out of memory unless you give it more).

Explanation

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.

Answer 3

Pyth, 13 bytes

eSm/%Mcd2Z.pQ

The time and storage complexity is really terrible. The first thing I do is to create a list with all permutations of the originally list. This takes n*n! storage. Input lists with length 9 already take quite a long time.

Try it online: Demonstration or Test Suite

Explanation:

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)

Answer 4

Mathematica, 95 93 87 83 79 60 58 bytes

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

Takes a few seconds for the larger examples.

Answer 5

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)

---

• the topper function is called by the main part.

• the input is in the form [. . .]

Answer 6

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)

---

• This apparently is longer, but oneliner and executive, and I managed to escape perms function because it takes forever.

• This function takes many reprises to run quiet well due to anonymous functions, I m open to suggestions here :)