c# - Permutation/Algorithm to Solve Conditional Fill Puzzle -

i've been digging around see if similar has been done previously, have not seen mirrored conditions. make swallowing problem little easier understand, i'm going apply in context of filling baseball team roster.

the given roster structure organized such: c, 1b, 2b, 3b, ss, 2b/ss (either or), 1b/3b, of, of, of, of, ut (can position)

every player has @ least 1 of non-backup positions (positions allow more 1 position) they're eligible , in many cases more 1 (i.e. player can play 1b , of, etc.). manager of team, has players on , want see if have room particular player @ of slots or if can move 1 or more players around open slot eligible.

my initial attempts use conditional permutation , collect in list possible unique "lineups" each player, updating open slots before moving next player. required (since order player moved affect positions available next player) list being looped through reordered , looped through again. still think way go, there number of pitfalls have snagged function.

the data start loop assume given is: 1. list of positions player being evaluated can player (the 1 being checked if can fit) 2. list of players on roster , positions each of eligible @ (i'm storing list of lists , using list index unique identifier of player) 3. list of positions open roster is

it's proven bigger headache anticipated. suggested me colleague situation have (which involves, on larger scale, conditional assignments each object) np-complete. not, since once player has been repositioned in particular lineup being tested, entire roster should not need iterated on again once player has moved. that's long , short of , decided open forums.

thanks can provide. due restrictions, can't post portions of code (some of legacy). is, however, being translated in .net (c# @ moment). if there's additional information necessary, i'll try , rewrite of short pieces of function post.

joseph g.

edited 07/24/2010 thank responses. did using genetic algorithm, abandoned because of amount of work go determination of ordinal results superfluous. ultimate aim of test determine if there is, in fact, scenario returns positive. there's no need determine relative benefit of each working solution.

i appreciate feedback on lack of familiarity context presented problem. actual model in distribution of build commands across multiple platform-specific build servers. it's accessible, i'd rather not why build tasks can executed on systems , why systems can execute types of build commands.

it appears have gotten gist of presenting, here's different model that's little less specific. there set of discrete positions in ordered array of lists such (i'll refer these "positions"):

((2), (2), (3), (4), (5), (6), (4, 6), (3, 5), (7), (7), (7), (7), (7), (2, 3, 4, 5, 6, 7))

additionally, there unordered array of lists (i'll refer "employees") can occupy 1 of slots if array has member in common ordered list assigned. after initial assignments have been made, if additional employee comes along, need determine if can fill 1 of open positions, , if not, if current employees can rearranged allow 1 of positions employee can fill made available.

brute force i'd avoid, because being on order of 40 - 50 objects (and increasing), individual determinations expensive calculate @ runtime.

i don't understand baseball @ sorry if i'm on wrong track. rounders though, there 2 positions play in rounders, batter or else.

have considered using genetic algorithms solve problem? @ solving np hard problems , work surprisingly rota , time schedule type problems well.

you have solution model can scored , manipulated great start genetic algorithm.

for more complex problems total permutations large calculate genetic algorithm should find near optimum or excellent solution (along lots , lots of other valid solutions) in short amount of time. although if wish find optimum solution every time, going have brute force in likelihood (i have skimmed problem may not case sounds is).

in example, have solution class, represents solution, ie line-up baseball team. randomly generate 20 solutions, regardless if valid or not, have rating algorithm rates solution. in case, better player in line-up score more worse player, , invalid line-ups (for whatever reason) force score of 0.

any 0 scoring solutions killed off, , replaced new random ones, , rest of solutions breed form new solutions. theoretically , after enough time pool of solutions should improve.

this has benefit of not finding lots of valid unique line-ups, rating them. didn't specify in problem need rate solutions, offers plenty of benefits (for example if player injured, can temporarily rated -10 or whatever). other players score based on quantifiable stats.

it's scalable , performs well.