2

I am struggling in making program in netlogo which produces the different combinations of turtles into two sets. For instance; there are total 10 turtles present in a system [0 1 2 3 4 5 6 7 8 9] and I want to produce different combinations of those turtles into two sets. {[0 6 7 8] [1 2 3 4 5 9]}, {[2 3 6 8 9] [0 1 4 5 7]}....... So on.

Any help would be really appreciated.

user2293224
  • 2,128
  • 5
  • 28
  • 52
  • @amaretto i have been trying to modify the code of existing netlogo code for combination and permutation. But no luck. – user2293224 Mar 01 '16 at 08:50
  • 1
    This is unclear. If there are only 3 turtles, do you want all possible combinations: {[0 1][2]} and {[0 2][1]} and {[0][1 2]}? This would be an odd thing to want NetLogo to do. Or do you just want to be able to have it produce one of these sets at random? – JenB Mar 01 '16 at 09:37
  • Here are some implementations in other languages: http://stackoverflow.com/questions/29656649/split-a-list-into-two-sublists-in-all-possible-ways Netlogo may be challenging to implement this. What are you using this for? If it's used as input for your simulation you may be able to write the solution to a file in another language with the existing code and read it in your simulation. Otherwise, just write a netlogo adaptation. – mattsap Mar 01 '16 at 16:38
  • @JenBF for three turtles it would be either one or two in subset. As you mentioned above – user2293224 Mar 02 '16 at 01:35

1 Answers1

0

This may be what you want. The below code removes duplicates by sorting the lists and removing duplicates (i.e it would remove [[1 2] [3]] and [[2 1] [3]] because it would sort the first list which would then be [1 2] which would cause for the match). Chop off an element and insert it into the left sublist and recurse.

You may imagine that each number in the list corresponds with a who. so you could do 

let alist [who] of turtles

Let me know if you have any questions

to-report permutate-sublist [added-whos remaining-whos]
  ifelse length remaining-whos = 1
  [
   report (list (list (sort added-whos) (sort remaining-whos)))
  ]
  [
    let result (list)
    foreach (sort remaining-whos)
    [
      let x ?
      let new-whos (sentence added-whos x)
      let new-remaining-whos (remove x remaining-whos)
      set result (sentence (list (list (sort new-whos) (sort new-remaining-whos))) result)
      set result (remove-duplicates (sentence (permutate-sublist new-whos new-remaining-whos) result))   
    ]
     report result
  ]
end

This is what happens when you print out the results for 

let alist (list 1 2 3 )
show permutate-sublist (list) alist

[[[2 3] [1]] 
 [[1 3] [2]] 
 [[3] [1 2]] 
 [[1 2] [3]] 
 [[2] [1 3]] 
 [[1] [2 3]]]
mattsap
  • 3,790
  • 1
  • 15
  • 36
  • Thaks. I will let you know if I have any question related to it. – user2293224 Mar 02 '16 at 01:37
  • 1
    The above method looks good problem comes in when there are 15 or more than 15 turtles in the system. program halts or computationally not tractable . – user2293224 Mar 02 '16 at 02:06
  • Correct. You're not going to be able to solve your problem with 15 or more turtles since the problem you're solving requires a combinatoric answer. If you constrain your problem, you may be able to create a more computationally friendly solution. Note the amount of memory that it requires to use to store all the partitions... If it uses alot of memory, your program will run slow. – mattsap Mar 02 '16 at 02:32
  • this limitation is because of netlogo architecture/internal working or is it also hold for other languages??? – user2293224 Mar 02 '16 at 04:25
  • This is a computation limitation. It holds for current computers. – mattsap Mar 02 '16 at 13:14
  • If this is a hindering issue, you may want to reconsider your approach and why you're creating all possible pairs. Generating a single pair at random is much simpler than generating all possible-pairs. You can figure out how many combinations for you algorithm there are using math... – mattsap Mar 02 '16 at 14:39
  • In my simulation i want to divide the turtles into two best possible groups. I want to consider all possible pairs and then calculate utility function of each pair and pick the best one. I dont think that by generating random pair would solve my problem. – user2293224 Mar 02 '16 at 19:14
  • You don't necessarily need to find all possible pairs. You should look into hill-climbing with random restarts or other local search algorithms with do exactly what you want. Many NP-problems run into computational issues, so essentially you sample the search space and tweak your solution to see if it's better repeatedly. See here:https://en.wikipedia.org/wiki/Local_search_(optimization) – mattsap Mar 02 '16 at 20:29