Anonymous user
Stable marriage problem: Difference between revisions
Added Objective-C version.
m (→{{header|XSLT 2.0}}: Page moved) |
(Added Objective-C version.) |
||
Line 2,264:
bob liked it so he put a ring on cath
</pre>
=={{header|Objective-C}}==
{{Works with|XCode 4.5.1}}
<lang objc>//--------------------------------------------------------------------
// Person class
@interface Person : NSObject {}
@property (nonatomic, strong) NSString* name;
@property (nonatomic, strong) NSArray* prefs;
@property (nonatomic, weak) Person* fiance;
@property (nonatomic) NSUInteger candidateIndex;
@end
@implementation Person
+ (Person *)named:(NSString *)name {
return [[Person alloc] initWithName:name];
}
- (id)initWithName:(NSString *)name {
if ((self = [super init])) {
_name = name;
_prefs = nil;
_fiance = nil;
_candidateIndex = 0;
}
return self;
}
- (NSString *)description {
return self.name;
}
@end
//--------------------------------------------------------------------
void doMarriage() {
Person *abe = [Person named:@"abe"];
Person *bob = [Person named:@"bob"];
Person *col = [Person named:@"col"];
Person *dan = [Person named:@"dan"];
Person *ed = [Person named:@"ed"];
Person *fred = [Person named:@"fred"];
Person *gav = [Person named:@"gav"];
Person *hal = [Person named:@"hal"];
Person *ian = [Person named:@"ian"];
Person *jon = [Person named:@"jon"];
Person *abi = [Person named:@"abi"];
Person *bea = [Person named:@"bea"];
Person *cath = [Person named:@"cath"];
Person *dee = [Person named:@"dee"];
Person *eve = [Person named:@"eve"];
Person *fay = [Person named:@"fay"];
Person *gay = [Person named:@"gay"];
Person *hope = [Person named:@"hope"];
Person *ivy = [Person named:@"ivy"];
Person *jan = [Person named:@"jan"];
abe.prefs = @[ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay ];
bob.prefs = @[ cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay ];
col.prefs = @[ hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan ];
dan.prefs = @[ ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi ];
ed.prefs = @[ jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay ];
fred.prefs = @[ bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay ];
gav.prefs = @[ gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay ];
hal.prefs = @[ abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee ];
ian.prefs = @[ hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve ];
jon.prefs = @[ abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope ];
abi.prefs = @[ bob, fred, jon, gav, ian, abe, dan, ed, col, hal ];
bea.prefs = @[ bob, abe, col, fred, gav, dan, ian, ed, jon, hal ];
cath.prefs = @[ fred, bob, ed, gav, hal, col, ian, abe, dan, jon ];
dee.prefs = @[ fred, jon, col, abe, ian, hal, gav, dan, bob, ed ];
eve.prefs = @[ jon, hal, fred, dan, abe, gav, col, ed, ian, bob ];
fay.prefs = @[ bob, abe, ed, ian, jon, dan, fred, gav, col, hal ];
gay.prefs = @[ jon, gav, hal, fred, bob, abe, col, ed, dan, ian ];
hope.prefs = @[ gav, jon, bob, abe, ian, dan, hal, ed, col, fred ];
ivy.prefs = @[ ian, col, hal, gav, fred, bob, abe, ed, jon, dan ];
jan.prefs = @[ ed, hal, gav, abe, bob, jon, col, ian, fred, dan ];
NSArray *men = [NSArray arrayWithArray:abi.prefs];
NSUInteger freeMenCount = men.count;
while (freeMenCount > 0) {
for (Person *guy in men) {
if (guy.fiance == nil // if he's available
&& guy.candidateIndex < guy.prefs.count) { // and he still has women to propose to
Person *gal = guy.prefs[guy.candidateIndex++]; // get the next woman in his preference list
if (gal.fiance == nil) { // she's available
gal.fiance = guy; // engage her to him
guy.fiance = gal; // engage him to her
freeMenCount--; // one less available guy
} else { // she's engaged
NSUInteger rankThisGuy = [gal.prefs indexOfObject:guy];
NSUInteger rankThatGuy = [gal.prefs indexOfObject:gal.fiance];
if (rankThisGuy < rankThatGuy) { // if she likes this guy better
gal.fiance.fiance = nil; // her old fiance is now available
gal.fiance = guy; // engage her to him
guy.fiance = gal; // engage him to her
}
}
}
}
}
for (Person *guy in men) {
printf("%s is engaged to %s\n", [guy.name UTF8String], [guy.fiance.name UTF8String]);
}
}
//--------------------------------------------------------------------
int main(int argc, const char * argv[])
{
@autoreleasepool {
doMarriage();
}
return 0;
}</lang>
{{out}}
<pre>bob is engaged to cath
fred is engaged to bea
jon is engaged to abi
gav is engaged to gay
ian is engaged to hope
abe is engaged to ivy
dan is engaged to fay
ed is engaged to jan
col is engaged to dee
hal is engaged to eve</pre>
=={{header|OCaml}}==
| |||