Maximal subset generated from constraint

x55.coffee

c = console.log.bind console




make_vertex = ({ k, addr, accd_set, remainder }) ->
    neighbors = {}
    remainder.reduce (acc, val, idx) ->
        # c val, idx

        # ((val + addr) % k) is 0


        x99 = accd_set.reduce (acc2, val2, idx2) ->
            if ((val + val2) % k) is 0
                acc2 = false
            acc2
        , true

        # c x99, 'x99'
        if x99 is true

            rem = [].concat remainder
            rem.splice idx, 1

            neighbors["#{val}"] = make_vertex
                k: k
                addr: val
                accd_set: [].concat(accd_set, [val])
                remainder: rem
    , {}

    { addr, accd_set, remainder, neighbors }


graph_the_set = (k, s) ->
    s.reduce (acc, val, idx) ->
        s1 = [].concat s
        s1.splice idx, 1
        acc["#{val}"] = make_vertex
            k: k
            addr: val
            accd_set: [val]
            remainder: s1
        acc
    , {}




k_33 = 7
rayy_33 = [278, 576, 496, 727, 410, 124, 338, 149, 209, 702, 282, 718, 771, 575, 436]



x55 = graph_the_set k_33, rayy_33
# c x55

Inspired by my attempts to solve this problem at hackerrank: https://www.hackerrank.com/challenges/non-divisible-subset/problem

Getting a JS heap out of memory error trying to graph that. Probably my implementation is bad and my algo is bad, but also might help to use Rust in this case, so will try that next, thinking more about the problem and possibly more efficient time or spacewise approaches.

My idea was graph out a tree (more precisely a directed acyclic graph with single root node) from each element, where each nodes's descendants exist if the constraint is satisfied for the accumulated/collected set up to that point. Then its a longest path problem, along with each node carries the size of one of the generated sets, so you could just find the maximum size of that property by exhaustively searching all nodes.

For efficiency, generally the problem is to accumulate some encoding of the already computed permutations, if that can avoid unnecessary computations that could save time and also memory space. I'm thinking some pipelining of this in such a way that an accumulator object can be passed through the graphing process. That would work in a single threaded context, the problem is more complex if multi-threading.

One important component to a solution is a technique to convert a set (any ordering of a set in an array or vector) into a unique string representation. If this exists on the graph already it wouldn't be computed. Actually in this way wouldn't need a graph at all, simply a list of these encodings of the sets generated that satisfy the constraint. The size is embedded in the encoded property names, which is all that is needed as a value.