'How to connect many short eulerian cycles into only a few longer ones?
I want to connect eulerian cycles into longer ones without exceed a value.
So, I have this eulerian cycles and their length in a list. The maximal length of a cycle can be for example 500. The length of all cycles added up is 6176.778566350282. By connecting them cleverly together there could be probably only 13 or 14 cycles. But I don't really know how I could do that. I tried to just add one cycle to another but there I got 21 cycles out. The problem is that if you have a cycle of these numbers for example: [8, 21, 9, 22, 8, 23, 9, 24, 8] and you want to integrate this cycle [10, 11, 12, 10] it will not work because in the first cycle there is no edge of the number 10. I just started then a new cycle with this numbers [10, 11, 12, 10] and saved [8, 21, 9, 22, 8, 23, 9, 24, 8] as one of the 21 result cycles. But with this method I don't really get a good result. What would be a cleverer way to solve this problem?
This is an example how the list of the short eulerian cycles looks like:
[([0, 1, 2, 0], 36.36630772776802), ([0, 3, 1, 4, 0], 93.83277865587606), ([0, 5, 1, 6, 0], 45.79353710664728), ([0, 7, 1, 8, 0], 49.60782827778143), ([0, 9, 1, 10, 0], 73.2674533926481), ([0, 11, 1, 12, 0], 75.52124688926921), ([0, 13, 1, 14, 0], 57.88021234723078), ([0, 15, 1, 16, 0], 62.21469065955568), ([0, 17, 1, 18, 0], 81.43809748917617), ([0, 19, 1, 20, 0], 98.88867905572438), ([0, 21, 1, 22, 0], 95.3596513800762), ([0, 23, 1, 24, 0], 116.15359042770964), ([2, 3, 4, 2], 49.106297391220245), ([2, 5, 3, 6, 2], 71.5422470782724), ([2, 7, 3, 8, 2], 50.237654764168), ([2, 9, 3, 10, 2], 71.36355688043689), ([2, 11, 3, 12, 2], 44.474596239420634), ([2, 13, 3, 14, 2], 103.42527218232905), ([2, 15, 3, 16, 2], 65.92444557445982), ([2, 17, 3, 18, 2], 83.30561323888043), ([2, 19, 3, 20, 2], 144.20150278029047), ([2, 21, 3, 22, 2], 131.70030082856), ([2, 23, 3, 24, 2], 141.63032737825358), ([4, 5, 6, 4], 42.10300780814433), ([4, 7, 5, 8, 4], 88.13162862262575), ([4, 9, 5, 10, 4], 29.40312423743285), ([4,
11, 5, 12, 4], 35.06685249446684), ([4, 13, 5, 14, 4], 83.54113932583394), ([4, 15, 5, 16, 4], 57.669814210895076), ([4, 17, 5, 18, 4], 85.16088821443248), ([4, 19, 5, 20, 4], 115.83839679838714), ([4, 21, 5, 22, 4], 96.32509817470469), ([4, 23, 5, 24, 4], 95.72504474795447), ([6, 7, 8, 6], 39.680511478789455), ([6, 9, 7, 10, 6], 78.55998969220359), ([6, 11, 7, 12, 6], 75.38181527864062), ([6, 13, 7, 14, 6], 65.59514045044449), ([6, 15, 7, 16, 6], 64.00893982862813), ([6, 17, 7, 18, 6], 82.99423226082924), ([6, 19, 7, 20, 6], 107.80803412093549), ([6, 21, 7, 22, 6], 104.34384551877056), ([6, 23, 7, 24, 6], 125.5684717784), ([8, 9, 10, 8], 52.130784276071026), ([8, 11, 9, 12, 8], 60.084249983353345), ([8, 13, 9, 14,
8], 80.8264707041123), ([8, 15, 9, 16, 8], 56.067658306081576), ([8, 17, 9, 18, 8], 87.79739969269264), ([8, 19, 9, 20, 8], 115.04095207094785),
([8, 21, 9, 22, 8], 100.28892183336735), ([8, 23, 9, 24, 8], 107.98171312085222), ([10, 11, 12, 10], 18.073592581964586), ([10, 13, 11, 14, 10],
86.59048377734861), ([10, 15, 11, 16, 10], 53.62896051047471), ([10, 17, 11, 18, 10], 79.42707393175432), ([10, 19, 11, 20, 10], 121.75438335508098), ([10, 21, 11, 22, 10], 103.13320830479722), ([10, 23, 11, 24, 10], 104.67092453129686), ([12, 13, 14, 12], 65.01056040398879), ([12, 15, 13, 16, 12], 73.92038351218434), ([12, 17, 13, 18, 12], 75.85986620162797), ([12, 19, 13, 20, 12], 99.9668143111241), ([12, 21, 13, 22, 12], 97.01425784207544), ([12, 23, 13, 24, 12], 113.28618776429398), ([14, 15, 16, 14], 53.12806382231952), ([14, 17, 15, 18, 14], 83.32318283097464), ([14,
19, 15, 20, 14], 59.489711796339975), ([14, 21, 15, 22, 14], 49.93204117686305), ([14, 23, 15, 24, 14], 59.39628730132421), ([16, 17, 18, 16], 76.30230372794964), ([16, 19, 17, 20, 16], 151.38369644764225), ([16, 21, 17, 22, 16], 137.27131752575687), ([16, 23, 17, 24, 16], 146.11467181532439), ([18, 19, 20, 18], 28.731124011957917), ([18, 21, 19, 22, 18], 51.78367537918862), ([18, 23, 19, 24, 18], 86.45013419422762), ([20, 21, 22,
20], 39.010097887844154), ([20, 23, 21, 24, 20], 63.48159687540681), ([22, 23, 24, 22], 22.283951753399037)]
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
