问题

我需要创建32位数字(有符号或无符号无关紧要,最高位永远不会被设置),每个数字必须设置给定的位数.

天真的解决方案

最简单的解决方案当然是从零开始.在循环内,数字现在增加1,计数位数,如果计数具有所需值,则数字存储到列表中,否则循环重复.如果找到足够的数字,则停止循环.当然这很好用,但是一旦所需位数变得非常高,它就会非常慢.

更好的解决方案

具有(比方说)5位的最简单的数字是设置前5位的数字.这个号码可以很容易地创建.在循环内,第一个位置位,数字向左移一个.这个循环运行5次,我找到第一个设置了5位的数字.接下来的几个数字也很容易创建.我们现在假装数字为6位宽,最高位数未设置.现在我们开始将第一个零位向右移动,因此我们得到101111,110111,111011,111101,1111110.我们可以通过在前面添加另一个0并重复此过程来重复此操作.0111110,1011110,1101110等.然而,这种方式的数字增长速度将超过必要的速度,因为使用这种简单的方法,我们省略了数字,如1010111.

那么有没有更好的方法来创建所有可能的排列,一种可以使用的通用方法,无论下一个数字将包含多少位,无论我们需要设置多少个位？

可能重复:
在排列中查找已排序的子序列

给定一个数组A,其中包含1,2,...,n的排列.如果A [i..j]
中出现的所有数字
都是连续数字(可能不是有序),则数组A的子块A [i..j] 被称为有效块.

给定阵列A = [7 3 4 1 2 6 5 8],有效块为[3 4],[1,2],[6,5],
[3 4 1 2],[3 4 1 2 6 5 ],[7 3 4 1 2 6 5],[7 3 4 1 2 6 5 8]

所以上面排列的计数是7.

给出O(n log n)算法来计算有效块的数量.

给出下表:

Index | Element
---------------
  1   |    A
  2   |    B
  3   |    C
  4   |    D

我们希望使用元素生成所有可能的排列(不重复).最终结果(跳过一些行)将如下所示:

  Results
----------
   ABCD
   ABDC
   ACBD
   ACDB
   ADAC
   ADCA

   ...

   DABC
   DACB
   DBCA
   DBAC
   DCAB
   DCBA

  (24 Rows)

你会怎么做？

我编写了一个函数来枚举给定列表的所有排列.您如何看待下面的代码？

def interleave(x:Int, l:List[Int]):List[List[Int]] = {
  l match { 
    case Nil => List(List(x))
    case (head::tail) =>
      (x :: head :: tail) :: interleave(x, tail).map(head :: _)
  }
}

def permutations(l:List[Int]):List[List[Int]] = {
  l match {
    case Nil => List(List())
    case (head::tail) =>
      for(p0 <- permutations(tail); p1 <- interleave(head, p0)) yield p1
  }
}

我正在学习回溯和递归,我坚持使用一种算法来打印字符串的所有排列.我用置换算法求解了它,但是我无法理解递归方法.我在网上搜索并找到了这段代码:

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); 
       }
   }
} 

这个算法基本上是如何工作的我无法理解？我甚至试过干跑!

如何应用回溯？

并且它比贝尔算法更有效地计算排列？

集合[1,2,3,...,n]总共包含n!独特的排列.

通过按顺序列出和标记所有排列,我们得到以下序列(即,对于n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"给定n和k,返回第k个排列序列.

例如,给定n = 3,k = 4,ans ="231".

那里有多种解决方案.但是它们都使用阶乘或者复杂度大于O(n),例如O(n!).如果你使用阶乘并在位置找到k /(n-1)!的数字,那么当n很大(n = 100)时会出现问题.这里n很大,(n-1)!溢出并变为0.结果,我得到一个零除错误...任何解决方案或算法？

这是我的代码:

public class KthPermutation {
    public String getPermutation(int n, int k) {
        // initialize all numbers
        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {
            numberList.add(i);
        }
        int fact = 1;   // set factorial of n-1

        for (int i = 1; i <= n-1; i++) {
            fact = fact * i;
        }   

        if ((long) …

写在Haskell中,这里的数据类型证明一个列表是另一个列表的排列:

data Belongs (x :: k) (ys :: [k]) (zs :: [k]) where
  BelongsHere :: Belongs x xs (x ': xs)
  BelongsThere :: Belongs x xs xys -> Belongs x (y ': xs) (y ': xys)

data Permutation (xs :: [k]) (ys :: [k]) where
  PermutationEmpty :: Permutation '[] '[]
  PermutationCons :: Belongs x ys xys -> Permutation xs ys -> Permutation (x ': xs) xys

有了a Permutation,我们现在可以置换记录:

data Rec :: (u -> *) -> [u] -> * where …

我正在实现几个数据结构和一个我要使用的原语如下:我有一个内存块A [N](它有一个可变长度,但我的示例需要100)并且在这个块中,有一个较小的部分C长度为K(比方说30),我想移动而不使用任何额外的内存.

另外的困难是,A"包裹",即C可以从A [80]开始,然后C的前20个元素是元素A [80..100],最后10个元素是元素A [ 0..10].此外,目标范围还可以以任何可能的方式"包裹"并与C重叠.另外,我不想使用超过一定数量的额外内存,一切都应该到位.此外,既不在目标范围内也不在源范围内的A部分可能包含重要的内容,因此也不能使用.所以一个案例如下:

A看起来像这样:

| 456789ABCDEF0123456789AB | ----- | 0123 |

应该转变为:

| 89AB | ----- | 0123456789ABCDEF01234567 |

只是将它委托给一个库或者使用库中的另一个数据结构不是一个选项,我想自己理解这个问题.在第一眼看来,我认为它可能不是微不足道的,但是一旦你区分了一些案例,它就会变得清晰,但现在我遇到了严重的麻烦.当然,如果它们不重叠或不包装,则存在微不足道的情况,但至少如果两者同时发生,则会变得混乱.您可以从一个空闲位置开始移动属于那里的部件,然后在其他地方创建另一个自由部件,并且很难跟踪您可以使用哪些部件.

也许我完全错过了一些东西,但即使是我的特殊情况,如果目标范围没有换行也有近100行(虽然它的一半是断言和注释)我可以更新它以便它也处理一般情况下一些额外的索引计算,但如果有人有一个优雅而简短的解决方案,我将不胜感激.直觉上我认为这应该是微不足道的,但我还没有看到最好的解决方案.

注意:有趣的情况当然是,如果C几乎和A一样大.如果| C | <N/2,这是微不足道的.

编辑:使用超过一定数量的额外标志/索引计数作为额外的内存,我想尽可能避免这种情况.

编辑:有些人想看我的代码.我的问题相当抽象,所以我不想发布它,但也许有人会看到如何改进它.这很糟糕,它只适用于目标从头开始(但是,可以很容易地改变)并且非常长的情况,但是它在O(n)中没有额外的存储器的情况下完成工作.

#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
  assert(source + size <= N);
  assert(target + size <= N);
  if (show_steps) {
    printf("Moving size %d from %d to %d.\n", size, source, target);
  }
  memmove(A + target, …

我正在努力有效地解决SPOJ问题64:排列.

设A = [a1,a2,...,an]是整数1,2,...,n的排列.如果ai> aj,则一对索引(i,j),1 <= i <= j <= n,是置换A的反转.我们给出整数n> 0和k> = 0.包含正好k次反转的n元素排列的数量是多少？

例如,恰好1次反转的4元素排列的数量等于3.

为了使给定的示例更容易看到,这里有三个4元素排列,正好有1个反转:

(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)

在第一个排列中,4> 3且指数4小于3的指数.这是单个反转.由于置换只有一次反转,因此它是我们试图计算的排列之一.

对于任何给定的n个元素序列,排列的数量是阶乘(n).因此,如果我使用强力n ²方法计算每个排列的反转次数,然后检查它们是否等于k,则该问题的解决方案将具有时间复杂度O(n!*n ²).

以前的研究

这个问题的一个子问题以前问这里在计算器上.给出了使用合并排序的O(n log n)解决方案,其计算单个排列中的反转次数.但是,如果我使用该解决方案来计算每个排列的反转次数,我仍然会得到O(n!*n log n)的时间复杂度,在我看来这仍然很高.

之前在Stack Overflow上也提到了这个确切的问题,但它没有收到任何答案.

如果没有数学公式来解决这个问题(我有点怀疑),那么我也看到人们提示有效的动态编程解决方案是可能的.使用DP或其他方法,我真的想制定一个比O(n!*n log n)更有效的解决方案,但我不确定从哪里开始.

欢迎任何提示,评论或建议.

编辑:我已经用DP方法回答了下面的问题来计算Mahonian数.

来自文档:

转置a.根据烫发更换尺寸.

返回的张量的维度i将对应于输入维度perm[i].如果perm没有给出,则设置为(n-1 ... 0),其中n是输入张量的等级.因此,默认情况下,此操作在2-D输入张量上执行常规矩阵转置.

但是我仍然有点不清楚我应该如何切割输入张量.例如,来自文档:

tf.transpose(x, perm=[0, 2, 1]) ==> [[[1  4]
                                      [2  5]
                                      [3  6]]

                                     [[7 10]
                                      [8 11]
                                      [9 12]]]

为什么perm=[0,2,1]产生1x3x2张量？

经过一些试验和错误:

twothreefour = np.array([ [[1,2,3,4], [5,6,7,8], [9,10,11,12]] , 
                        [[13,14,15,16], [17,18,19,20], [21,22,23,24]] ])
twothreefour

[OUT]:

array([[[ 1,  2,  3,  4],
        [ 5,  6,  7,  8],
        [ 9, 10, 11, 12]],

       [[13, 14, 15, 16],
        [17, 18, 19, 20],
        [21, 22, 23, 24]]])

如果我转置它:

fourthreetwo = tf.transpose(twothreefour) 
with …