javascript - 最佳小便池策略

Question

这是一个 interactive page描述问题和 academic paper复习数学。

问题大致可以描述如下。

给定一个任意长度的 bool 值数组，表示 n 个相邻的小便池，true 的值表示已占用， 的值false 表示空，在给定任何配置的情况下，您将如何构建算法来填充此数组，同时:

• 通过让一个人尽可能远离两侧的其他小便器，最大限度地保护每个人的“隐私”。

• 通过确保配置在最后可能的时间饱和来尽可能长时间地维护此隐私。

• 面对多个次优选择，优先考虑两边没有相邻小便池的小便池，而不是仅空置的相邻小便池。

为了简单起见，我标记了这个 javascript，但任何代码或伪代码都可以。

var urinals = Array
    .apply(null, new Array(n))
    .map(Boolean.prototype.valueOf,false);

---

编辑 - 在这里发现一个相关问题:

Optimal Seating Arrangement Algorithm

Answer 1

尽可能接近解决方案:

var urinalFinder = function(urinals){
    var gaps = new Array(), last = null;
    for(var i = 0; i < urinals.length; i++){
        last = gaps.length ? gaps[gaps.length - 1] : 0;
        if(last < 0 && !urinals[i] || last > 0 && !!urinals[i] || last == 0) 
            gaps.push(0); // push if new sequence of vacant or occupied
        // negatives are occupied count & positives vacant count
        gaps[gaps.length - 1] += !!urinals[i] ? -1 : 1; 
    }

    // find the first index of the largest gap
    var maxGapSize = Math.max.apply(Math, gaps),
        maxGapGapsIdx = gaps.indexOf(maxGapSize),
        isFirst = maxGapGapsIdx === 0,
        isLast = maxGapGapsIdx === gaps.length - 1,
        maxGapIdx = 0;

    if(maxGapSize < 1) return false; // no gaps available

    var gapPoint = maxGapSize > 3 
            ? Math.ceil(maxGapSize / 3) // per xkcd suggestion
            : isFirst && maxGapSize === 2
                ? 1
                : isLast && maxGapSize === 2 ? 2 : Math.ceil(maxGapSize / 2);

    // find where our chosen gap begins in input array
    for(var i = 0; i < maxGapGapsIdx; i++)
        maxGapIdx += Math.abs(gaps[i]);

    var result = maxGapIdx + gapPoint - 1; // arrays are zero-indexed

    return result;
};

例如，应用于填充 9 个空位的数组将像这样填充它们:

var foo = [0,0,0,0,0,0,0,0,0]; // nine values
for(var i = 0; i < foo.length; i++)
    foo[urinalFinder(foo)] = i+1;

[4, 6, 1, 7, 2, 8, 3, 9, 5]

并不总能产生最佳结果(有时不同的放置可能会导致稍后移动几步就饱和)并且不喜欢末端小便器，但在分散值并尽可能长时间地保持最小缓冲方面做得很好.