"""
npp_mk_inst: generate a series of benchmark instances for number partitnioning

files easy*.dat:
  - random numbers with n/2 bits (for sets with n elements)
  - large number of perfect partitions
  - easy instances

files hard*.dat:
  - random numbers with n bits (for sets with n elements)
  - small/null number of perfect partitions
  - hard instances

Notice that according to S.Mertens, "The easiest hard problem",
the critical number of bits in random generated integers,
for a problem with N items is:

def kc(N):
    return 1 - (log2(N) - log2(pi/6))/(1.*N)

"""
import random

def mk_data_trivial(n, min_value, max_value):
    """make random data number partitioning: trivial case"""
    return [min_value + int(random.random() * (max_value-min_value+1)) for i in range(n)]

def mk_data(n, nbits):
    """make random data number partitioning: using integers with 'nbits' bits"""
    data = []
    for i in range(n):
        value = 0
        for b in range(nbits):
            if random.random() >= 0.5:
                value += 2**b
        data.append(value)
    return data

def mk_data_decimal(n, nbits):
    """make random data number partitioning: using integers with 'nbits' bits"""
    data = []
    for i in range(n):
        value = 0
        for b in range(nbits):
            value = 10*value + int(random.random()*10)
        data.append(value)
    return data

def write_data(filename,data):
    print filename
    f = open(filename, 'w')
    for i in data:
        print >>f, i
    f.close()


# names of the instances
EASY = ["easy%04d.dat" % n \
        for n in [10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000]]
HARD = ["hard%04d.dat" % n \
        for n in [10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000]]
DECIMAL = ["n%03dd%02de%02d.dat" % (n,b,e)\
        for b in [10,12,14] for n in [15,25,35,45,55,65,75,85,95,105] for e in range(10)]

if __name__ == "__main__":
    random.seed(1)

    for n in [10,20,30,40,50,60,70,80,90,100,200,300,400,500,600,700,800,900,1000]:

        # easy instances
        data = mk_data(n,n/2)
        data.sort()
        filename = "easy%04d.dat" % n
        write_data(filename,data)

        # hard instances
        data = mk_data(n,n)
        data.sort()
        filename = "hard%04d.dat" % n
        write_data(filename,data)

    for b in [10,12,14]:
        for n in [15,25,35,45,55,65,75,85,95,105]:
            for e in range(10):
                data = mk_data_decimal(n,b)
                data.sort()
                filename = "n%03dd%02de%02d.dat" % (n,b,e)
                write_data(filename,data)