算法：如何space固定长度圆形数组中的新元素尽可能远离现有元素？

Question

我希望 space 元素之间的距离尽可能远。

假设数组的长度为 360。

Element 1 goes at position 0.
Element 2 goes at position 180.
Element 3 goes at position 90 (or 270).
Element 4 goes at position 270 (or 90).
Element 5 goes at position 45.
Element 6 goes at position 135.
Element 7 goes at position 225.
Element 8 goes at position 315.
Element 9 goes at position 23.
Element 10 goes at position 68.

等等。

假设长度为 100。

Element 1 goes at position 0.
Element 2 goes at position 50.
Element 3 goes at position 25 (or 75).
Element 4 goes at position 75 (or 72).
Element 5 goes at position 13.
Element 6 goes at position 38 (or 75).
Element 7 goes at position 63.

等等。

用户将传入数组长度和元素编号。所以 f(2,360) 会 return 180 而 f(7,100) 会 return 63.

给定数组长度和元素个数，输出位置的方法是什么？

编辑：我的具体应用是，在我知道会有多少元素之前，我试图为每个元素选择不同色调的颜色，同样 spaced。

编辑 2：我的问题陈述引起了一些混乱。为简单起见，我在演示解决方案中使用了整数，但实际上我并不需要整数输出。我的错。我会将解决此问题的解决方案标记为正确的，但我应该警告我自己还没有检查过。我已经检查了下面的答案并且它有效，尽管它是 0 索引和 returns 小数。

Answer 1

你要找的这个函数，我们就叫它f(i,n)，可以递归定义如下（假设索引从0开始，log(x)输出[的base 2 log的floor =13=]):

f(0,n)=0
f(1,n)=n/2
if(i%2==0){
   f(i,n)=f(i/2,n)-f(2^(log(i)-1),n)/2
}
else{
   f(i,n)=f(i/2,n)+f(2^(log(i)-1),n)/2
}

希望对您有所帮助！

Answer 2

这里有一个不重复的非递归解法，只要0 < i <= n。它是尽可能以与语言无关的方式编写的，所以如果你不知道 ruby 也没关系：

# round, but if fraction is .5 then floor.
def round2 x
  double = 2*x
  double == double.round ? x.floor : x.round
end

# i is 1-based. 0 < n.
def f( i, n )
  j = (i-1) % n # convert to 0-based and mod n index j
  nsig = 1 << Math.log2(n).floor # highest bit in n
  if (j&nsig) == 0
    j2 = 1 << Math.log2((j<<1)|1).floor # smallest power of 2 > j
    angle = n*(j2^((j<<1)|1)) / j2.to_f # to_f converts to float
    return angle.round
  else
    return round2(n*((nsig^j)+0.5)/(nsig^n))
  end
end

[360,100].each do |n|
  puts "\nFor array length #{n}:\n"
  (1..12).each do |i|
    puts 'Element %d goes to position %d.' % [ i, f(i,n) ]
  end
end

输出：

For array length 360:
Element 1 goes to position 0.
Element 2 goes to position 180.
Element 3 goes to position 90.
Element 4 goes to position 270.
Element 5 goes to position 45.
Element 6 goes to position 135.
Element 7 goes to position 225.
Element 8 goes to position 315.
Element 9 goes to position 23.
Element 10 goes to position 68.
Element 11 goes to position 113.
Element 12 goes to position 158.

For array length 100:
Element 1 goes to position 0.
Element 2 goes to position 50.
Element 3 goes to position 25.
Element 4 goes to position 75.
Element 5 goes to position 13.
Element 6 goes to position 38.
Element 7 goes to position 63.
Element 8 goes to position 88.
Element 9 goes to position 6.
Element 10 goes to position 19.
Element 11 goes to position 31.
Element 12 goes to position 44.

基本思想是可视化项目围绕一个圆圈的放置。如果您查看基于 0 的索引的位，那么您可以快速看到索引的位长度与它们围绕圆放置的位置之间的模式。

例如元素5、6、7、8放置如下。首先减1，使它们从0开始，观察位：

这些都是长度为 3（位大小）的索引。它们被放置在圆周的 45°、135°、225°、315° 位置。然后只是算术和舍入转换为循环数组内的索引。

这是 JavaScript 中的一个版本：http://jsfiddle.net/gfj7Lpya/3/

对于 OP 编辑 1 和 2，在 JavaScript 中：

// i is 0-based. Return value in [0,1).
function f( i )
{
  if( i === 0 ) return 0;
  var ndigits = Math.floor(Math.log(i)/Math.LN2); // in base 2
  return ((1<<ndigits^i)<<1|1) / (2<<ndigits);
}

JSFiddle：http://jsfiddle.net/gfj7Lpya/4/

例如，要将其应用于 360 的数组 "length"，只需将输出相乘：

360 * f(8) // 22.5

Answer 3

Phil 的解决方案让我开始思考。我认为这稍微好一点，因为它只需要一个日志。在 JavaScript:

// Returns the position of element n
// as far away as possible from other elements
// with total space totalSpace
function getPlacement(n, totalSpace) {
    if (n == 0) return 0;

    var divisions = Math.pow(2, log2Floor(n) + 1);
    var position = ((2 * (n + 1 - (divisions / 2))) - 1);
    return position * ( totalSpace / divisions );
}

// Quickly returns the floor of the base 2 log
function log2Floor(x) {
  if (x === 0) return -Infinity;
  for (var i = 0; i < 32; ++i) {
    if (x >>> i === 1) return i;
  }
}

算法：如何space固定长度圆形数组中的新元素尽可能远离现有元素？

Algorithm: How to space new elements in fixed length circular array as far away from existing elements as possible?

algorithm