仅使用 3 个元素形成数组的方法有多少种？

Question

我们需要找出可以组成仅包含 3 个元素（1,2 和 3）的 N 长度数组 (A) 的方法数。

数组的相邻元素如何放置在数组中几乎没有限制：

特定类型的相邻元素对的数量 (A[i], A[i + 1]) 不能超过问题陈述中给出的数量。

example :

1, 2 : 2 (we can have at most 2 adjacent-pairs of value [1, 2] in the array)
1, 3 : 3
2, 1 : 1
2, 3 : 0 (we cannot have any adjacent-pairs of value [2, 3] in entire array)
3, 1 : 4
3, 2 : 3

对于A[i] == A[i + 1]类型的相邻元素，它们可以在数组中出现任意次数

1, 1 : inf
2, 2 : inf
3, 3 : inf

示例案例：

Input :

N = 3

1, 2 : 1 
1, 3 : 1
2, 1 : 1
2, 3 : 0 
3, 1 : 0
3, 2 : 0

Output :

Explanation :

[1, 2, 1] , here { (1,2) : 1, (2,1) : 1 }, so valid 
[1, 2, 2]
[1, 1, 2]
[2, 1, 2]

[1, 3, 3] , here { (1,3) : 1, (3,3) : 1 }, so valid 
[1, 1, 3]
[2, 1, 3] , here { (2,1) : 1, (1,3) : 1 }, so valid 

[2, 1, 1] , here { (2,1) : 1, (1,1) : 1 }, so valid 
[2, 2, 1]     

[1, 1, 1] , here { (1,1) : 2 }, so valid, as adj-pairs (x, x) can be any number of times.
[2, 2, 2]
[3, 3, 3]

All other combinations of 1,2,3 are invalid like :
[3, 1, 1], [2, 3, 1], etc.

Constraints

1 <= N <= 10^6

0 <= limit[i][j] <= 10^5

where N = array length and limit[i][j] = number of pairs of type (i, j)

Pseudocode :

main() :
   ways = 0;
   for(p = 1; p <= 3; p++) :
       ways += num_ways(p, 1, n, A, limit);
   return ways;


num_ways(prev, i, n, A[], limit[][]) :
  
  if(i == n) return 1;
  
  ways = 0;
  for(e = 1; e <= 3; e++):
      if(limit[prev][e] > 0) 
          limit[prev][e] -= 1;
          ways += num_ways(e, i + 1, A, limit);
          limit[prev][e] += 1;

  return ways;

, where limit[i][j] means max number of adjacent-pairs of value (i, j) that can be present in array

伪代码解释：

我尝试使用递归（蛮力）解决这个问题，即在每个函数调用插入任何元素(1,2,3) 在索引 i 并检查 (A[i - 1], A[i]) 对是否没有超过问题陈述中给出的限制，如果 yes then return else 继续通话 func() 而 i != n.

这种方法很好，但它给出了 TLE（超出时间限制）错误，因此它不是找出形成数组的方法数的最佳方法。

Is there any other efficient way to solve this problem ?

Answer 1

从计算的角度来看，您面临两个问题：内存 space（见下文）和性能。

候选号码个数为m=3^N (mmax=3^Nmax=3^(10^6)).

您必须建立一个约束列表，ic=1...nc。显然，最大约束数为ncmax=3^2=9。如果对 (i,i) 将始终不受约束，则 ncmax=3*(3-1)=6。进一步不受约束的每一对都计入此总数。您的“标准”订单 (ic,pair) 似乎是 {(1,(1,2)), (2,(1,3)), (3,(2,1)), (4,(2,3)), (5,(3,1)) , (6,(3,2))}.

每个约束由：

约束函数，它取一个数字i和returnscondition/pair的出现次数pc(i,ic)（或pc(i,pair)）来验证。
最大允许出现次数 pcmax(ic)（或 pcmax(pair)）。

在你的第一个“示例案例”中，数字 i=121，pc(121,(1,2))=1, pcmax((1,2))=1 -> ok.

一种非常暴力的方法（没有递归）：

nways = 0
for i in 1:m   # (you have to find how to loop on the very large number of numbers)
    for ic in 1:nc
        c = pc(i,ic)
        cmax = pcmax(i)
        if (c <= cmax)
            nways += 1

算法的一些（可能重要的）优化是可能的，也许通过使用递归。

在pc(i,ic)的计算中，如果该方法遍历第i个pair进行计数，也可以通过pcmax(ic)提前“失败”退出，而不完全检查i中的所有pair .
如果你的 pcmax(ic) 值总是比 N 小。你提到 1<=pcmax(pair)<=P，P=10^5。 P<你说 P 和 N 之间没有关系，所以原则上不是这种情况。
请注意，您的“示例案例”使用 pcmax((2,3))=pcmax((3,1))=pcmax((3,2))=0，这与您最后的一般条件 1<=pcmax(pair) 相矛盾<=P.
还有吗？

没有进一步的 specification/restriction 问题，我不确定你能做得更好。

内存space

1 位候选号码 -> 2 位 (1,2,3)。（这是 space 的 25% 浪费）
10^6 digits -> 10^6*2 bits = 10^6/4 bytes ~ 256 kB，如果在一个字节中打包 4 位数字。或者您可以使用每个数字一个字节，最多占用 ~1MB。

Answer 2

我将采用的方法是不创建实际数组。相反，我会通过分析您的限制来处理它。

1, 2 : 2
1, 3 : 3
2, 1 : 1
2, 3 : 0
3, 1 : 4
3, 2 : 3

因此您的系统中只允许有限数量的转换。

所以我的出发点是计算所有可能的转换组合，并为每个组合关联一个 min-length n。这可以使用一些蛮力方法来执行，尽管可能有也可能没有更有效的方法。

暴力法输出的示例应如下所示...

min-length 2 个转换：

1, 2
1, 3
2, 1
3, 1
3, 2
So, n-2 pattern count = 5.

min-length 3 个转换：

1, 2, 1
1, 3, 1
1, 3, 2
2, 1, 2
2, 1, 3
3, 1, 2
3, 1, 3
3, 2, 1
So, n-3 pattern count = 8.

一旦我们计算出每个最小长度的所有可能组合计数，我们就会根据实际输入 n 执行排列数学运算。我们可以重用我们创建的原始结构来非常快速地对 n 的多个输入执行计算。

例如，当 n = 3 时，我们从 3 开始 null-transitions。然后我们为不需要 min-length n 的转换排列添加 8。然后我们计算 min-length n - 1、n - 2 等的排列，直到 n - x = 2。排列是通过将每个转换的位置偏移 space 来计算的。即 n = 3 和 min-n = 2，多余的 space = 1，所以我们可以将转换 left/right 移动 1，给我们 2 个模式而不是 1。所以因为有 5长度为 2 的模式，每个模式都可以转换为 2 个模式，这将为我们提供 10 个模式。所以我们有 10 + 8 + 3 = 21.

为了进一步阐明数学，我将在 n-3 模式中使用 n = 10。我们有 9 个转换槽和 2 个转换，可以应用置换数学：

第一个转换可能发生在 9 个转换槽中的前 8 个中的任何位置。选择哪个插槽决定了第二个转换的去向，但现在让我们忽略它。然后这变成 9!/7!。但是，这包括所有乱序组合，因此我们想进一步将其除以 2！。所以我们有 9 * 4 = 36 种组合，* n-3 种模式的模式计数 = 36 * 8。将此添加到 n-2 种模式、n-4 种模式等...

这将概括为：

sum(i: n ... 1) { patternCount(i) * ((n - 1)!)/(n - i - 1)!/i! }

Answer 3

您的问题是我们如何才能更有效率地做到这一点。我假设您指的是运行时，而不是内存。我将提出一个解决方案，它可能会很快，但代价是内存消耗非常高。一般来说，他们通常是一个牺牲另一个。

我会迭代地构建它。首先让我们准备好我们需要的数据。我们需要什么？我们将构建一个映射，其中键是左边的数字，值是映射本身。第二个映射在任何可能的正确值之间映射到它可能的数量。让我们根据您的示例生成这样的地图：

1, 2 : 2 (we can have at most 2 adjacent-pairs of value [1, 2] in the array)
1, 3 : 3
2, 1 : 1
2, 3 : 0 (we cannot have any adjacent-pairs of value [2, 3] in entire array)
3, 1 : 4
3, 2 : 3

我们将生成地图：

Map(
  1 -> Map(2 -> 2, 3 -> 3),
  2 -> Map(1 -> 1),
  3-> Map(1 -> 4, 2 -> 3)
)

鉴于该地图，现在我们可以开始构建解决方案了。

我们将启动一个元组序列。我们将其称为所有可能的解决方案。这些元组会是什么？第一个元素将是最后添加到结果序列的数字。第二个值将是剩余的可能对。这意味着在每次迭代中，我们需要从地图中减少使用的对。

在每次迭代中，我们都会将队列的长度添加到结果中，因为我们总是可以通过重复最后一个元素来完成序列，直到我们到达 N-length 序列。

我假设我们已经有了地图和剩余的对，我将其称为 remainingPairs。现在，让我们写一些代码：

intermediateQueue = Queue((1 to N).map(i => remainingPairs))
numWays = N
for (int i = 0; i < n - 1; i++) { // The first iteration was the line above
  for (int j = 0; j < intermediateQueue.length; j++) {
    (lastInSeries, currentRemainingPairs) = intermediateQueue.pull()
    toContinueWith = currentRemainingPairs.get(lastInSeries) // that is a map from the next element to the count it can still be used
    for ((value, repeatCount) <- toContinueWith) {
      if (repeatCount > 0) {
        newToContinueWith = toContinueWith.copy // This is very important!! otherwise you'll override yourself between iterations.
        newToContinueWith[value] = newToContinueWith[value] - 1
        newRemainingPairs = remainingPairs.copy
        newRemainingPairs[lastInSeries] = newToContinueWith
        intermediateQueue.add((value, newRemainingPairs))
      }
    }
    numWays += iterlength
  }
}

让我们尝试使用给定的示例来跟进该代码。我们已经构建了初始地图。

我们用 (1 -> map, 2 -> map, 3 -> map) 启动队列

i=0
numWays = 3 // That represents the series (1,1,1) (2,2,2) (3,3,3) 
  j = 0
  (lastInSeries, currentRemainingPairs) = (1, Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3)))
  toContinueWith = Map(2 -> 2, 3 -> 3)
    (value, repeatCount) = (2, 2)
      newToContinueWith = Map(2 -> 1, 3 -> 3)
      newRemainingPairs = Map(1 -> Map(2 -> 1, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3))
      intermediateQueue.add(2, newRemainingPairs)
    (value, repeatCount) = (3, 3)
      newToContinueWith = Map(2 -> 2, 3 -> 2)
      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 2), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3))
      intermediateQueue.add(3, newRemainingPairs)
  j = 1
    (lastInSeries, currentRemainingPairs) = (2, Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3)))
  toContinueWith = Map(1 -> 1)
    (value, repeatCount) = (1, 1)
      newToContinueWith = Map(1, 0)
      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 0), 3-> Map(1 -> 4, 2 -> 3))
      intermediateQueue.add(1, newRemainingPairs)
  j = 2
    (lastInSeries, currentRemainingPairs) = (3, Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(2 -> 3)))
  toContinueWith = Map(1 -> 4)
    (value, repeatCount) = (1, 4)
      newToContinueWith = Map(1, 3)
      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 0), 3-> Map(1 -> 3, 2 -> 2))
      intermediateQueue.add(1, newRemainingPairs)
  toContinueWith = Map(2 -> 3)
    (value, repeatCount) = (2, 3)
      newToContinueWith = Map(2, 2)
      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 0), 3-> Map(1 -> 4, 2 -> 2))
      intermediateQueue.add(2, newRemainingPairs)
  numWays += 5 // That represents the following: (1,2,2) (1,3,3) (2,1,1) (3,1,1) (3,2,2)
i = 1

我们继续这样的另一个循环，并得到以下有效系列：

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

P.S

我们甚至可以通过删除空映射来稍微改进该算法。它将节省大量计算和内存。

Answer 4

因为你问的是计数而不是排列列表，所以很容易解决，如果你把它分成两步：

预先计算所有可能的组合，直到没有什么可以组合为止。这会为每个 length = 2,3,...
要获得给定 len 的计数，请使用达到所需长度的解决方案，并使用更小的 len 扩展解决方案。幸运的是，这可以通过一个简单的公式来完成，该公式被称为将 k 个球分配到 n 个桶中。 x = (( n over k )) = ( k+n+1 over n-1) 将该值 x 乘以变体计数并将其相加。

这是一个有效的示例代码：

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class A3 {

    static class P {
        List<Integer> list;
        Map<Integer, Integer> avail;

        public P(List<Integer> list, Map<Integer, Integer> pair2n) {
            this.list = list;
            avail = pair2n;
        }
        
        public String toString() {
            return list.toString();
        }
    }
    
    // sequences with count as array of {a, b, n}
    int limited[][] = {
            {1,2,1},
            {1,3,1},
            {2,1,1},
            {2,3,0},
            {3,1,0},
            {3,2,0}
    };

    // lookup   a*10 + b -> n
    private TreeMap<Integer, Integer> pair2n;

    // precalculated combinations
    private List<ArrayList<P>> precalc = new ArrayList<>();
    
    /**
     * Simple main stub
     * @param args unused
     */
    public static void main(String[] args) {
        A3 a3 = new A3();
        a3.init();
        a3.precalc();
        a3.solve();
    }

    /**
     * Fill map from array.
     */
    private void init() {
        pair2n = new TreeMap<Integer, Integer>();
        for (int []x : limited) {
            pair2n.put(x[0] * 10 + x[1], x[2]);
        }
    }

    /**
     * Calculate all valid combinations until all counters are 0.
     */
    private void precalc() {
        // pre-calculate solutions without 1,1 2,2 and 3,3 until all counters are 0
        int prelen = 0;
        for (Integer n : pair2n.values()) {
            prelen += n;
        }
        
        System.out.println("precalc 2.." + prelen);
        ArrayList<P> current = new ArrayList<>();
        current.add(new P(Arrays.asList(1), pair2n));
        current.add(new P(Arrays.asList(2), pair2n));
        current.add(new P(Arrays.asList(3), pair2n));
        precalc.add(current);
        
        for (int i = 2;; ++i) {
            ArrayList<P> next = new ArrayList<>();
            for (P p : current) {
                for (Entry<Integer, Integer> e : p.avail.entrySet()) {
                    // count > 0 and last number matches current sequence
                    if (e.getValue() > 0 && e.getKey() / 10 == p.list.get(p.list.size() - 1)) {
                        ArrayList<Integer> al = new ArrayList<Integer>(p.list);
                        al.add(e.getKey() % 10);
                        Map<Integer, Integer> map = new TreeMap<>(p.avail);
                        map.put(e.getKey(), e.getValue() - 1);
                        P np = new P(al, map);
                        next.add(np);
                    }
                }
            }
            if (next.isEmpty())
                break;

            precalc.add(next);
            System.out.println("len=" + i);
            System.out.println("with " + next.size() + " permutations");
            System.out.println(next);
            current = next;
        }
    }

    /**
     * precalc contains sequences of different numbers.
     * => any extension of n -> n,n will create an unique solution.
     * 
     * the difference to current length defines how many combinations are insertable.
     */
    private void solve() {
        for (int in = 1;in <= 99;++in) {
            BigInteger wantedLen = new BigInteger(Integer.toString(in));
            BigInteger count = BigInteger.ZERO;
            for (ArrayList<P> pc : precalc) {
                P p = pc.get(0);
                int ik = p.list.size();
                if (ik > in)
                    break;
                
                BigInteger currentLen = new BigInteger(Integer.toString(ik));
                
                BigInteger k = wantedLen.subtract(currentLen);
                BigInteger n = currentLen;
                BigInteger addend = nOverK(n.add(k).subtract(BigInteger.ONE), n.subtract(BigInteger.ONE));
                
                BigInteger len = new BigInteger(Integer.toString(pc.size()));
                System.out.println(currentLen + " -> " + wantedLen + ": " + addend + " * " + len);
                count = count.add(addend.multiply(len));
            }
            System.out.println("Total permutations for " + in + " = " + count);
        }
    }

    /**
     * Helper to calc the faculty.
     * @param k a value
     * @return the faculty.
     */
    private BigInteger faculty(BigInteger k) {
        BigInteger r = BigInteger.ONE;
        while (k.compareTo(BigInteger.ONE) > 0) {
            r = r.multiply(k);
            k = k.subtract(BigInteger.ONE);
        }
        return r;
    }

    /**
     * Calculate n over k.
     * @param n 
     * @param k
     * @return ( n
     *           k )
     */
    private BigInteger nOverK(BigInteger n, BigInteger k) {
        BigInteger fn = faculty(n);
        BigInteger fk = faculty(k);
        BigInteger fnk = faculty(n.subtract(k));
        BigInteger r = fn.divide(fnk.multiply(fk));
        return r;
    }
}

仅使用 3 个元素形成数组的方法有多少种？

Number of ways to form array using only 3 elements?

arrays

algorithm

math

dynamic-programming

combinatorics