创建分配唯一项的算法
Creating an algorithm for distributing unique items
我不确定如何在我的代码中创建一个特定问题的算法，所以我创建了这个难题
- 有3个饼干怪物。
- 每个怪物都有一个袋子，里面有从0到有限数量(假设是100)的随机饼干。
- 有许多不同类型的cookie，但我们不知道有多少(我们可以在生成cookie后发现)。
- 每个怪物要从自己的袋子里吃1块饼干
- 没有其他怪物可以得到相同类型的饼干。
- 如果两个或两个以上的怪物在他们的袋子里没有任何独特的味道，低指数的怪物应该得到饼干，而其他(s)不得到饼干。
- 我们要确保每个怪物得到一个饼干如果可能的话。
.
// A cookie maker for good measure:
function cookieMaker(quant) {
// Fill in your own flavours...
const flavours = [...]
const cookies = []
for(let i = 0; i < quant; i++) {
cookies.push(flavours[Math.floor(Math.random() * flavours.length)])
}
return cookies
}
// This is our function
function pickCookies(monsters) {
...
}
pickCookies([
{
name: 'Fluffy',
cookies: ['choco', 'vanilla', 'blueberry']
},
{
name: 'Pillowpants',
cookies: ['choco', 'vanilla']
},
{
name: 'Pinky',
cookies: ['choco']
}
])
// Should return:
[
{
name: 'Fluffy',
eat: 'blueberry'
},
{
name: 'Pillowpants',
eat: 'vanilla'
},
{
name: 'Pinky',
eat: 'choco'
}
]
// Note, that it should also work if you shuffle the list.
我为你做了一个json格式的口味列表:
你会如何解决这个难题?
修改我似乎遗漏了至少一个细节，所以如果你已经开始做了，我将在这里添加任何更改，以免突然更改规则使任何人感到困惑:
- #1怪物应该尝试从袋子的顶部(较低的数组索引)，如果可能的话。
我发现你的问题很有趣，所以我通过创建这个算法来尝试一下:
用语言- 为每个怪物创建一个数组，其中包含所有cookie类型在他们的包(删除重复)。
- 对于每个怪物，计算他们的选择(可用的口味)。
- 选择数量最少的怪物。
- 对于每个选项，检查有多少其他怪物共享此风味。
- 取主人数量最少的味道，让怪物吃掉它。
- 从剩余怪物的袋子中移除味道。
- 从步骤2重复，直到[没有其他饥饿的怪物留下]或[每个怪物留下没有更多的口味可用]。
第一枪
var monsters = [{name:'Fluffy'}, {name:'Pillowpants'}, {name:'Pinky'}],
flavors = ['choco', 'vanilla', 'blueberry', 'peanut butter'],
maxNumberOfCookies = 6;
$('#generateBtn').click(generateExample);
generateExample();
function generateExample() {
// Fill each monster's bag
for(var i=0; i<monsters.length; i++) monsters[i].cookies = cookieMaker();
// 3, 2, 1, bon appetit!
var res = pickCookies(monsters);
displayResults(monsters, res);
}
function cookieMaker() {
var cookies = [],
// The quantity is random for each monster
quant = Math.floor(Math.random() * maxNumberOfCookies);
for(var i=0; i<quant; i++) {
cookies.push(flavors[Math.floor(Math.random() * flavors.length)])
}
return cookies;
}
function pickCookies(monsters) {
var res = [];
// List flavors available for each monster
for(var i=0; i<monsters.length; i++) {
var m = monsters[i],
flavorsInBag = [];
for(var j=0; j<m.cookies.length; j++) {
if(flavorsInBag.indexOf(m.cookies[j]) < 0) {
flavorsInBag.push(m.cookies[j]);
}
}
res.push({name: m.name, flavors: flavorsInBag, eat: false});
}
while(!allMonstersAte(res) && !noMoreFlavors(res)) {
// Take the monster with the smallest number of options
var monsterWithLeastFlavors = false;
for(var i=0; i<res.length; i++) {
if(!res[i].flavors.length) continue;
if(!monsterWithLeastFlavors
|| res[i].flavors.length < monsterWithLeastFlavors.flavors.length) {
monsterWithLeastFlavors = res[i];
}
}
// Select the flavor owned by the fewest monsters
var flavorWithLeastOwners = monsterWithLeastFlavors.flavors[0],
fewestNbOfOwners = res.length;
for(var i=0; i<monsterWithLeastFlavors.flavors.length; i++) {
var nbOfOwners = getNbOfOwners(monsterWithLeastFlavors.flavors[i], res);
if(nbOfOwners < fewestNbOfOwners) {
flavorWithLeastOwners = monsterWithLeastFlavors.flavors[i];
fewestNbOfOwners = nbOfOwners;
}
}
makeMonsterEat(monsterWithLeastFlavors, flavorWithLeastOwners, res);
}
return res;
}
// Returns true if all monsters have a property "eat" != false
function allMonstersAte(res) {
return !res.some(function(monster){ return !monster.eat; });
}
// Returns true if all monsters have no flavor left to choose from
function noMoreFlavors(res) {
return !res.some(function(monster){ return monster.flavors.length; });
}
// Returns the number of monsters who have that flavor
function getNbOfOwners(flavor, monsters) {
return monsters.filter(function(monster){
monster.flavors.indexOf(flavor)>-1;
}).length;
}
function makeMonsterEat(monster, flavor, res) {
monster.flavors = [];
monster.eat = flavor;
for(var i=0; i<res.length; i++) {
res[i].flavors = res[i].flavors.filter(function(fl){ return fl != flavor; });
}
}
function displayResults(monsters, res) {
var initial = "";
for(var i=0; i<monsters.length; i++) {
initial += '<b>' + monsters[i].name + '''s bag contains:</b> '
+ (monsters[i].cookies.length ? monsters[i].cookies.join(', ') : '<span style="color:red">NOTHING</span>') + '<br>';
}
var result = "";
for(var i=0; i<res.length; i++) {
result += '<b>' + res[i].name + ' ate:</b> '
+ (res[i].eat ? res[i].eat : '<span style="color:red">NOTHING</span>')
+ '<br>';
}
$('#result').html('<h2>Initial state</h2>'
+ initial
+ '<h2>Result</h2>'
+ result
);
}*{margin: 0; padding: 0}
body{font-family: Arial, Helvetica, sans-serif; padding: 1em; font-size: 14px}
h2{font-size: 18px; margin: .3em 0}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<button id="generateBtn">Generate new example</button>
<div id="result"></div>更实用的方法
我不知道这是不是你想要的，但我试过了。
var monsters = [{name:'Fluffy'}, {name:'Pillowpants'}, {name:'Pinky'}],
flavors = ['choco', 'vanilla', 'blueberry', 'peanut butter'],
maxNumberOfCookies = 6;
$.getJSON('https://cdn.rawgit.com/demux/ad32c612b303aa12d1cdf043225fa1d2/raw/3a037fb7ad30d8a383526ebc62b3671a1656c06d/flavours.json')
.done(init);
function init(data) {
flavors = data;
$('body').html('<button id="generateBtn">Generate new example</button><div id="result"></div>');
$('#generateBtn').click(generateExample);
generateExample();
}
function generateExample() {
// Fill each monster's bag
for (var i = 0; i < monsters.length; i++)
monsters[i].cookies = cookieMaker(Math.floor(Math.random() * maxNumberOfCookies));
// 3, 2, 1, bon appetit!
var res = pickCookies(monsters);
displayResults(monsters, res);
}
function cookieMaker(quant) {
var cookies = [];
for (var i = 0; i < quant; i++) {
cookies.push(flavors[Math.floor(Math.random() * flavors.length)])
}
return cookies;
}
/*
* Returns a new Array of monsters who ate unique cookies
*/
function pickCookies(monsters) {
var res = getMonstersWithFlavors(monsters);
while (!allMonstersAte(res) && !noMoreFlavors(res)) {
var monsterIndex = indexOfMonsterWithLeastFlavors(res),
flavor = flavorWithLeastOwners(res[monsterIndex].flavors, res);
for (var i = 0; i < res.length; i++) {
if (i == monsterIndex) res[i] = makeMonsterEat(res[i], flavor);
else res[i] = removeFlavor(res[i], flavor);
}
}
return res;
}
/*
* Returns a new Array of monsters with their flavors
*/
function getMonstersWithFlavors(monsters) {
return monsters.map(function(monster) {
return {
name: monster.name,
flavors: removeDuplicates(monster.cookies),
eat: false
};
});
}
/*
* Returns a new Array without duplicates
*/
function removeDuplicates(arr) {
return Array.from(new Set(arr));
}
/*
* Returns the index of the monster with least flavors
*/
function indexOfMonsterWithLeastFlavors(monsters) {
var tmp = { monsterIndex: -1, count: false };
for (var i = 0; i < monsters.length; i++) {
if (!monsters[i].flavors.length) continue;
if (!tmp.count || monsters[i].flavors.length < tmp.count) {
tmp = { monsterIndex: i, count: monsters[i].flavors.length };
}
}
return tmp.monsterIndex;
}
/*
* Returns the flavor owned by least monsters
*/
function flavorWithLeastOwners(flavors, monsters) {
var tmp = { flavor: '', count: false };
for (var i = 0; i < flavors.length; i++) {
var nbOfOwners = getNbOfOwners(flavors[i], monsters);
if (!tmp.count || nbOfOwners < tmp.count) {
tmp = { flavor: flavors[i], count: nbOfOwners };
}
}
return tmp.flavor;
}
/*
* Checks if all monsters have a property "eat" != false
*/
function allMonstersAte(res) {
return !res.some(function(monster) {
return !monster.eat;
});
}
/*
* Checks if all monsters have no flavor left to choose from
*/
function noMoreFlavors(res) {
return !res.some(function(monster) {
return monster.flavors.length;
});
}
/*
* Returns the number of monsters who have that flavor
*/
function getNbOfOwners(flavor, monsters) {
return monsters.filter(function(monster) {
monster.flavors.indexOf(flavor) > -1;
}).length;
}
/*
* Returns a new monster Object with the cookie they ate
*/
function makeMonsterEat(monster, flavor) {
return {
name: monster.name,
flavors: [],
eat: flavor
};
}
/*
* Returns a new monster Object without the cookie flavor
*/
function removeFlavor(monster, flavor) {
return {
name: monster.name,
flavors: monster.flavors.filter(function(fl) {
return fl != flavor
}),
eat: monster.eat
};
}
function displayResults(monsters, res) {
var initial = "";
for (var i = 0; i < monsters.length; i++) {
initial += '<b>' + monsters[i].name + '''s bag contains:</b> ' +
(monsters[i].cookies.length ? monsters[i].cookies.join(', ') : '<span style="color:red">NOTHING</span>') + '<br>';
}
var result = "";
for (var i = 0; i < res.length; i++) {
result += '<b>' + res[i].name + ' ate:</b> ' +
(res[i].eat ? res[i].eat : '<span style="color:red">NOTHING</span>') +
'<br>';
}
$('#result').html('<h2>Initial state</h2>' +
initial +
'<h2>Result</h2>' +
result
);
}*{margin: 0; padding: 0}
body{font-family: Arial, Helvetica, sans-serif; padding: 1em; font-size: 14px}
h2{font-size: 18px; margin: .3em 0}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<h2>Loading...</h2>这个问题被称为"一个不同代表的系统"，有一些关于它们的定理和至少几个已发表的算法来解决它。你可能会发现霍尔的婚姻定理很有趣。在上下文中总结一下:
当且仅当，对于每一个怪物的子集，在这些怪物的袋子里有更多不同类型的饼干，然后在这个子集里有怪物，每个怪物都有可能吃饼干。
@blex写了一个算法，是一个很好的贪心逼近算法。当可能的cookie类型的数量远远大于怪物的数量时，它应该总是有效的，但是当这些数量非常接近并且非常大时，它通常会失败。
下面是一个人为的例子，其中@blex的算法在8个怪物和8种不同的cookie类型时失败了。马上，蓝咬做出了错误的选择，他必须选择香草，但他选择了巧克力，这个选择没有可能的解决方案，因为Fluffy, Fred, Jub和Pillowpants是四个怪物的子集，只有三种选择(燕麦片，蓝莓和花生酱)。
初始状态Blubite的袋子里有:巧克力，香草
松软的袋子里有:巧克力，蓝莓，花生酱
弗雷德的袋子里有:燕麦片、蓝莓、花生酱
Jub的袋子里有:燕麦片，蓝莓，花生酱
枕头裤的袋子里有:燕麦片、蓝莓、花生酱
Pinky的袋子包含:香草，燕麦片，糖，朗姆酒，绿色
Scuzzy的袋子包含:香草，燕麦片，糖，朗姆酒，绿色
Ziffu的袋子包含:香草，燕麦片，糖，朗姆酒，绿色
Blubite ate: choco
毛茸茸的食物:蓝莓
弗雷德吃了:燕麦片
Jub吃:花生酱
枕头裤吃了:NOTHING
Pinky吃:香草
软糖:糖
紫芙:朗姆酒
蓬松的食物:choco
弗雷德吃了:燕麦片
Jub吃:蓝莓
枕裤吃了花生酱
小萍吃了糖
Scuzzy:朗姆酒
紫紫:绿色
有一本书包含了在一般情况下正确解决它的两种算法，这里是1956年的一篇学术论文，其中包含了这两种算法之一的原始描述。我不打算在JavaScript中实现这个算法，但如果我需要休息一下，我可能会在以后重新审视它。
相关文章：
- 循环比赛位置算法
- javascript扫雷器floodfill算法不能正常工作
- 使用onkeyup JS事件检查输入的值是否唯一
- 当同一浏览器的两个实例浏览时，Javascript页面如何具有唯一的ID
- Lodash映射并返回唯一
- Node JS中的排名系统算法
- 在数据库中循环值时，为输入框获取唯一值
- 查找仅适用于原始图像的图像放大算法的名称
- 在数组的 2/3 上调用自身的排序算法
- 如何从数组中查找唯一对象
- 正在为循环创建唯一id
- 获取唯一值并使用javascript计算金额总和
- JavaScript:从对象数组中获取唯一值及其计数
- Luhn算法的实现
- 算法:从数组(javascript/angular）中按当前日期获取上一个和下一个事件
- ng重复中的ng模型-初始化唯一作用域属性
- 加速单纯形算法
- 从名字和姓氏生成简短的唯一人类可读 ID 的算法
- 具有唯一结果的两个数字组合的精简算法
- 创建分配唯一项的算法
