Solving a recursive method

user_7248917 0
Viewed 61

I have three variables

Group-Set of Persons ex: {{David, Sebastian, Yousef}, {Boris, Mark}}

Person-Set ex: {David, Mark, Sebastian, Boris, Yousef}

Relation-Set ex: {{David, Mark}, {Sebastian, Boris}}

A Group-Set cannot have any person that are friends with each other.

A Group-Set cannot have duplicates.

I need to create a divide method thats called

divide(person-set, relation-set) and returns a group-set as the example above.

It needs to be solved recursively and loops are not allowed.

I already have a method called areFriends(Person, Person) that returns a boolean if they are friends or not.

This is what I got so far:

divide(ps, r){
    divide(ps, r, gs){

    let p1 = getRandom(ps);
        p2 = getRandom(ps);

    if(areFriends(p1, p2) = false){
      gs.add(p1);
      gs.add(p2);
    }


    remove(p1, ps);
    if(getRandom(ps) != 0){
    divide(ps, r, gs);
  }
}

I've been dealing with this problem for a long time now and really need help with it. Thanks!

pseudocode recursion algorithm
1 Answers

Based on a new constraint (without no loop constraint), we need an indicator (g_ind) for considering groups in the function:

divide(ps, r, g = [[]], g_ind = 0)

    p <- empty
    if there is any person in ps:
        p <- take the first person from ps
    else:
        return
    
    if g_ind >= len(g):
        // all current divisions in g have a friend of p
       g.add([p]) // add a new division with initial member p
       remove p from ps
       divide(ps, r, g, 0)
       return  
    else if any friends of p in r exists in g[g_ind]:
       divide(ps, r, g, ++g_ind)
       return
    else:
        g[g_ind].add(p)
        remove p from ps
        divide(ps, r, g, 0)
        return
user_37688710
Related