javascript - 最佳小便池策略

这是描述问题的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

最佳答案

我离解决方案很近:

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]

并不总是产生最佳结果(有时不同的放置位置可能会使以后的移动几步饱和)，并且不利于小便池，但是可以很好地散布周围的值并在尽可能短的时间内保持最小的缓冲。