Question

挑战：编写一个程序或函数，给定正整数 n、t、b、c，计算 1..n 的排列，其中：

恰好 t 个数字处于其原始位置
恰好有 b 个数字比其原始位置高
恰好有 c 个数字比其原始位置低

输入：四个非负整数 n、t、b、c，任意合理格式。

输出：满足所有条件的有效排列的数量。

限制：

t, b, c ≥ 0
t + b + c = n（你可以假设输入满足这一点）

测试用例：

n=3, t=1, b=1, c=1 → 3 
n=2, t=2, b=0, c=0 → 1  
n=3, t=0, b=2, c=1 → 1  
n=4, t=1, b=2, c=1 → 4

对于 n=3、t=1、b=1、c=1 的示例解释：

三个有效排列为：

[1,3,2]: 1 fixed, 3 higher, 2 lower
[2,1,3]: 3 fixed, 2 higher, 1 lower
[3,2,1]: 2 fixed, 1 lower, 3 higher

这是，因此字节数最短的解决方案获胜！

对于您的示例 ( n=3, t=1, b=1, c=1)，这不[3,2,1]也是一个有效的排列 (2=固定；1=较低；3=较高) 吗？对于测试用例，我也得到了4。🤔6在n=4, t=1, b=2, c=1这四个之后我会缺少哪两个：[[1,3,4,2], [2,3,1,4], [2,4,3,1], [3,2,4,1]]？ —

Answer 1

，13

Œ!>,<ɗJ$§⁼ɗƇL

一个二元链接，n在左边和[b, c]右边接受（t由于 $t + b + c = n$ t + b + c = n保证）。

（删除尾随的来查看排列L）

如何？

Œ!>,<ɗJ$§⁼ɗƇL - Link: n; [b, c]
Œ!            - all permutations of {[1..n]}
           Ƈ  - filter keep those for which:
          ɗ   -   last three links as a dyad - f(P, [b, c]):
       $      -     last two links as a monad - f(P):
      J       -       indices -> [1..n]
     ɗ        -       last three links as a dyad - f(P, [1..n]):
  >           -         {P} greater than {[1..n]} (vectorises)
    <         -         {P} less than {[1..n]} (vectorises)
   ,          -         pair these
        §     -     sums -> [#higher, #lower]
         ⁼    -     {that} equals {[b,c]}?
            L - length

潜在的更快方法

我相信这是正确的，但我还没有严格地证明过这一点……

首先计算一下数字， $P_{n, t}$ P_{n,t}，排列 $n$ n元素恰好 $t$ t固定点为

磷 n, t = n ！ \sum 我 = t n - 1 （ 一世 - t ） t ！ （ i - t ） ！

P_{n,t} = n! \sum_{i=t}^n \frac{-1^{(i-t)}}{t!(i-t)!}

然后计算剩余的错位数 $n - t$ n-t元素（因为它们都需要移动）， $D_{n - t}$ D_{n-t}作为：

德 n - t = （ n - t ） ！ \sum 我 = 0 n - t - 1 （ n - t - i ） （ n - t - i ） ！

D_{n-t} = (n-t)! \sum_{i=0}^{n-t}\frac{-1^{(n-t-i)}}{(n-t-i)!}

（或者利用 $D_{n - t}$ D_{n-t}是最接近的整数 $\frac{(n - t)!}{e}$ \frac{(n-t)!}{e}，如果你能得到 $e$ e任意精度。

然后计算错位的数量 $(n - t)$ (n-t)正是 $b$ b超出范围（或等同于 $c = t - n - b$ c=t-n-b超出，因为这是对称的）， $D_{n - t, b}$ D_{n-t,b}使用递归公式：

德 s + 1, x = x 德 点 ​ ​ + （ s + 1 - x ） 德 s, x - 1 + 秒 德 s - 1, x - 1

D_{s+1,x} = x D_{s,x} + (s+1-x) D_{s,x-1} + sD_{s-1,x-1}

（根据 OEIS 条目 – 是否存在此条目的封闭形式？）

现在最终计数结果如下：

磷 n , t 德 n - t , b 德 n - t

\frac{P_{n,t}D_{n-t,b}}{D_{n-t}}

或者，等价地

磷 n , t 德 n - t , c 德 n - t

\frac{P_{n,t}D_{n-t,c}}{D_{n-t}}

我现在还不想在 Jelly 中打高尔夫球，但打高尔夫球的一种方法是利用以下事实：

德 是 = \sum 我 = 0 是 德 是 ， 我

D_z = \sum_{i=0}^{z} D_{z,i}

Answer 2

，11字节

ɾṖƛż₍><Ṡ;$O

         $O # Count the number of times [b, c] occurs in
ɾṖ          # Permutations of 1...n
  ƛ     ;   # For each
   ż        # Take the range from 1 to n
    ₍--     # Pair
     >      # Whether each is higher than its index
      <     # or lower
       Ṡ    # Sum these, giving [b, c]

Answer 3

+ `-n`，8字节

↕x-±→Ħ-ž

将输入作为n [b,t,c]。

↕x-±→Ħ-ž
↕           Find a permutation of [0,1,...,n-1]
 x          Push [0,1,...,n-1]
  -         Subtract
   ±        Signum
    →       Increment
     Ħ      Histogram; count occurrences of 0,1,2,...
      -     Subtract [b,t,c]
       ž    Check if all elements are 0

-n计算解决方案的数量。

Answer 4

，97 字节

Tr[1^Select[b={##2};s=Range@#;#-s&/@Permutations@s,(f=#;Count[f,u_/;Sign@u==#]&/@{0,1,-1}==b)&]]&

Answer 5

，22 20 14

按顺序将目标作为数组c,t,b。

o á ËüÈgYÃmÊeV

o á ËüÈgYÃmÊeV     :Implicit input of integer U=n and array V=[c,t,b]
o                  :Range [0,U)
  á                :Permutations
    Ë              :Map
     ü             :  Group & sort by
      È            :  The following function
       g           :    Sign of difference with
        Y          :      0-based index
         Ã         :  End grouping
          m        :  Map
           Ê       :    Length
            eV     :  Is equal to V?
                   :Implicit output of sum of resulting array

原始20字节

保留这个，因为我非常喜欢比较运算符数组的构造。以t、b&c作为反向顺序的数组。

o á £VË¶XèEg§¬o³i>Ã×

o á £VË¶XèEg§¬o³i>Ã×     :Implicit input of integer U=n and array V=[c,b,t]
o                        :Range [0,U)
  á                      :Permutation
    £                    :Map each X
     VË                  :  Map each D in V
       ¶                 :    Is D equal to
        Xè               :      Count the elements in X that return true when compared to their 0-based indices thusly
          Eg             :        Index E into
            §            :          "<="
             ¬           :          Split
              o          :          Modify the last element
               ³         :            Triplicate (to give the strictly-equal-to comparison operator. Duplicating would also work, to give the loosely-equal-to operator.)
                i>       :          Prepend ">"
                  Ã      :  End inner map
                   ×     :  Reduce by multplication
                         :Implicit output of sum of resulting array

这会产生所有排列吗？问题明确指定了 n ≤ 500 的上限，我认为这意味着大约 1.2e+1134 个排列。 — 
@doubleunary，是的，根据我们能够假设无限的时间和记忆的共识。 — 
好的，那么也许首先在问题中指定上限是没有意义的。 —

Answer 6

，24字节

/+≡(/↧⬚0=°⊚+1±-°⊏)⧅≠⟜⇡⊙¤

/+≡(/↧⬚0=°⊚+1±-°⊏)⧅≠⟜⇡⊙¤
                   ⧅≠⟜⇡     # generate all permutations of 0..n-1
  ≡(              )          # for each row:
              ±-°⊏          #     get the sign of the comparison to the original indices
         °⊚+1               #     find the counts of [>, =, <]
    /↧⬚0=               ⊙¤  #     do they match [b, t, c] (filling empty spaces with 0)?
/+                          # count those which are true

Answer 7

3，154 147字节

import itertools as I
f=lambda n,t,b,c,q=0,R=range:sum(sorted((r[a]>a)-(r[a]<a)for a in R(n))==[-1]*c+[0]*t+b*[1]for r in I.permutations(range(n)))

\endgroup

1

\begingroup
由于您执行了两次此操作，因此您创建了一个变量R=range，但最后忘记使用它（I.permutations(range(n))可以是I.permutations(R(n))-4 个字节），并且您还有一个未使用的变量,q=0，您可以删除另外 -4 个字节。:) 此外，您可以将导入放在f=lambda 下方，再放置 -2 个字节，从而将其放在标题中。由于挑战保证 $n = t + b + c$ n=t+b+c，您还可以将校验从改为==[-1]*c+[0]*t+b*[1]，[c:]==[0]*t+b*[1]再增加 -3 个字节。总计：
\endgroup

–

|

Answer 8

，12

Lœʒā.S1Ý¢Q}g

输入为 $n$ n和 $[t, b]$ [t,b]（没有 $c$ c，自从 $t + b + c = n$ t+b+c=n是有保证的。

或。

如果我们将这四个值都作为输入，则通过将( ) 替换为( ) 并按顺序获取第二个输入，它会长 1 个1Ý[0,1]®1Ÿ[-1,0,1] $[c, t, b]$ [c,t,b]：
或。

解释：

L          # Push a list in the range [1, first (implicit) input-integer n]
 œ         # Get all permutations of this list
  ʒ        # Filter this list of permutation-lists by:
   ā       #  Push a list in the range [1,length] (without popping)
    .S     #  Vectorized compare each value at the same positions:
           #   -1 if a<b; 0 if a==b; 1 if a>b
      1Ý   #  Push pair [0,1]
        ¢  #  Count how many times those occur in the list of compares
         Q #  Check whether this list equals the second (implicit) input-pair
  }g       # After the filter: pop and push the length
           # (which is output implicitly as result)

Answer 9

，61字节

⊞υ⊞ＯＥ³Ｎ…·¹ＮＦυ«≔⊟ιηＦη«≔⊕⁻›κＬη‹κＬηζ¿§ιζ⊞υ⊞ＯＥι⁻λ⁼μζ⁻η⟦κ⟧»Ｍ¬η→»Ｉⅈ

链接为代码的详细版本。按顺序输入c t b n。说明：

⊞υ⊞ＯＥ³Ｎ…·¹ＮＦυ«

使用数组和从到的c t b范围开始广度优先搜索。1n

≔⊟ιηＦη«

循环遍历范围内的剩余元素。

≔⊕⁻›κＬη‹κＬηζ

查看当放置在下一个倒数位置时，此元素是否会固定、更高或更低。

¿§ιζ

如果有可用位置容纳该类型元素，那么……

⊞υ⊞ＯＥι⁻λ⁼μζ⁻η⟦κ⟧

…减少位数并从范围中删除该元素，然后将结果推送到搜索列表。

»Ｍ¬η→

保持完全有效排列的数量。

»Ｉⅈ

输出最终计数。

Answer 10

JavaScript (ES7)，107 字节

期望(n)([t,b,c])。简单的强力搜索。

n=>g=(c,k=0,m=2**n-1)=>m?(h=j=>m>>j&&h(-~j)+(m>>j&1&&g(C=[...c],k+1,m^1<<j,C[j>k?2:j<k|0]--)))``:c=="0,0,0"

代码高尔夫 – 计算约束排列 – 代码高尔夫

10 个回答
10

，13

如何？

潜在的更快方法

，11字节

+ `-n`，8字节

，97 字节

，22 20 14

原始20字节

，24字节

3，154 147字节

，12

，61字节

JavaScript (ES7)，107 字节

代码高尔夫 – 计算约束排列 – 代码高尔夫

10 个回答 10

，13

如何？

潜在的更快方法

，11字节

+ -n，8字节

，97 字节

，22 20 14

原始20字节

，24字节

3，154 147字节

，12

，61字节

JavaScript (ES7)，107 字节

10 个回答
10

+ `-n`，8字节