高尔夫代码:找到加权中位数的最短代码? [英] Code Golf: Shortest code to find a weighted median?

问题描述

我尝试打高尔夫球.

确定∑W_i*|X-X_i|的最小值的问题简化为找到权重为w[i]的x[i]列表的加权中位数(有关定义，请参见下文).您将如何用最短，最简单和最漂亮的程序来做到这一点?

The problem of finding the minimum value of ∑W_i*|X-X_i| reduces to finding the weighted median of a list of x[i] with weights w[i] (see below for definition). How will you do that with a shortest, simplest and most beautiful program?

这是我的代码的原始外观(解释在问题的答案和简短内容中版本发布为以下答案之一).

Here's how my code looked originally (explanation is in the answer to the question and short version is posted as one of the answers below).

    #define zero(x) ( abs(x) < 1e-10 )  /* because == doesn't work for floats */

    float sum = 0;
    int i;

    for (i = 0; i < n; i++) 
         sum += w[i];
    while (sum > 0) 
         sum -= 2*w[--i];

    right = x[i]             // the rightmost minimum point
    left  = ( zero(sum) && zero(w[i]-w[i-1]) ) ? x[i-1] : right;
    answer = (left + right) / 2;

(实际上，正如您看到的变量i和sum被重用一样，已经对其进行了重大优化)

(Actually, it's been already heavily optimized as you see variables i and sum reused)

浮点数和整数:不同的语言具有不同的浮点算术标准，因此我将问题重新表示为x[i]和w[i]为整数，您可以如果愿意，则返回答案值的两倍(始终为整数).您可以返回，打印或将答案分配给变量.

Floats and integers: different languages have different floating point arithmetic standards, so I reformulate the problem to have x[i] and w[i] to be integers and you can return twice the value of the answer (which is always integer) if you prefer. You can return, print or assign the answer to variable.

加权中位数的定义和说明:

• 长度为n的排序数组x[i]的中位数为x[n/2]或(x[n/2-1/2]+x[n/2+1/2])/2，具体取决于n是奇数还是偶数
• 未排序数组的中位数是排序后数组的中位数(是的，但我们的数组已排序)
• 具有正整数权重w[i]的x[i]加权中位数被定义为较大数组的中位数，其中每个x[i]出现都已更改为w[i]出现了x[i].

• Median of sorted array x[i] of length n is either x[n/2] or (x[n/2-1/2]+x[n/2+1/2])/2 depending on whether n is odd or even
• Median of unsorted array is the median of array after sort (true, but our array is sorted)
• Weighted median of x[i] with integer positive weights w[i] is defined as the median of larger array where each occurrence of x[i] has been changed into w[i] occurrences of x[i].

提出问题的原因之一是，我认为最合适的语言将使用lambda进行琐碎的数组求和和迭代.我认为功能性语言可能是合理的，但是对此我不确定-因此这是问题的一部分.我希望看到类似的东西

One of the reasons for asking is that I assume the most suitable language will have trivial array summation and iteration with lambdas. I thought a functional language could be reasonable, but I'm not sure about that - so it's part of the question. My hope is to see something like

    // standard function   add  :=  (a,b) :-> a + b 
    myreduce := w.reduce  
        with:  add  
        until: (value) :-> 2*value >= (w.reduce with:add)
    answer = x [myreduce  from:Begin] + x [myreduce  from:End]

Dunno，如果有任何语言，这是可能的，并且实际上更短.

Dunno if there's any language where this is possible and is actually shorter.

static int n = 10;
for (int j = 0; j < n; j++) {
        w[j] = j + 1;
        x[j] = j;
}

答案:6或12.

static int n = 9;
int w[n], x[n] ;
for (int j = 0; j < n; j++) {
    w[j] = j + ((j<6) ? 1 : 0);
    x[j] = j + 1;
}

答案:6.5或13.

推荐答案

J

继续并将其直接输入到解释器中.提示是三个空格，因此缩进的行是用户输入的.

J

Go ahead and type this directly into the interpreter. The prompt is three spaces, so the indented lines are user input.

   m=:-:@+/@(((2*+/\)I.+/)"1@(,:(\:i.@#))@[{"0 1(,:(\:i.@#))@])

我在其他答案中使用的测试数据:

The test data I used in my other answer:

   1 1 1 1 m 1 2 3 4
2.5
   1 1 2 1 m 1 2 3 4
3
   1 2 2 5 m 1 2 3 4
3.5
   1 2 2 6 m 1 2 3 4
4

将测试数据添加到问题中

The test data added to the question:

   (>:,:[)i.10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8  9
   (>:m[)i.10
6
   (([+<&6),:>:)i.9
1 2 3 4 5 6 6 7 8
1 2 3 4 5 6 7 8 9
   (([+<&6)m>:)i.9
6.5

---

   i =: (2 * +/\) I. +/

第一个索引，使得总和大于或等于累加和的两倍.

First index such that total sum is greater than or equal to double the accumulated sum.

   j =: ,: (\: i.@#)

列表及其反义词.

   k =: i"1 @ j @ [

第一个索引，使-见上-左引数及其反序.

First indices such that -see above- of the left argument and its reverse.

   l =: k {"(0 1) j @ ]

分别从正确的参数及其反面提取的那些索引.

Those indices extracted from the right argument and its reverse, respectively.

   m =: -: @ +/ @ l

结果列表总和的一半.

这篇关于高尔夫代码:找到加权中位数的最短代码?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！