直角坐标系(一种特殊的直角坐标系产品)-以可重复的样式从数组中选择元素 [英] Cartesian power (a special Cartesian product) -- choose elements from array, in repeatable style

问题描述

输入:
有一个长度为n的输入数组(假定没有重复的元素).

Input:
There is an input array (assume there are no repeated elements) of length n.

输出:
并想打印所有可能的相同长度的数组n由输入数组中的元素组成，每个输入元素可以在输出数组中多次使用.

Output:
And would like to print all possible array of the same length n consists of elements from input array, each input element could be used multiple times in the output array.

提示:

• n在多个输入之间是可变的.

• n is variable among multiple inputs.

输入数组:[0, 1, 2]

预期输出:

• 000
• 001
• 002
• 010
• 011
• 012
• 020
• 021

• 022

• 000
• 001
• 002
• 010
• 011
• 012
• 020
• 021

• 022

100

122

200

有3 * 3 * 3 = 27个组合，对于长度为n的数组，通常为n^n.

There are 3 * 3 * 3 = 27 combinations, or in general n^n for array with length n.

• 如何以小写输入n(< = 5)来打印(可能是递归样式)?
• 如何有效地针对大型输入n进行打印，而不会出现堆栈溢出(可能只有一个循环)?
  例如，当n = 9时，有387420489个输出，则程序应能够处理此类输入.
• 应该怎么称呼这个问题?这不是典型的排列，因为元素是可重复的.欢迎修改标题.

• How to print this for small input n (<=5), probably in recursive style?
• How to print this for large input n efficiently, without overflow in stack, probably with a single loop?
  e.g when n = 9, there are 387420489 outputs, the program should be able to handle such inputs.
• What should this problem be called ? It's not a typical permutation since the elements are repeatable. Modification to the title is welcomed.

推荐答案

一个循环很难.递归可能是最直观的方法.但这是一个具有两个循环的迭代版本，使用Python，但避免了itertools的魔术功能，因此它不是所有特定于语言的:

A single loop is hard. Recursive might be the most intuitive approach. But here is an iterative version with two loops, using Python but avoiding magic functionality from itertools so it's not all that language-specific:

a = [0]*n
while(True):
  for i in range(n):
    a[i] += 1
    if a[i] == n:
      a[i] = 0
    else:
      break
  else:
    break
  print("".join(map(str, reversed(a))))

想法如下:从右到左为您的数字编制索引(因此，其中的reversed调用).递增最右边的数字.只要您达到那里的n极限，就重置为零，但将数字再增加一位.这实际上是使用带进位的长加法来加1.没有更多进位时退出内部循环.当您没有明确退出内部循环时，即当您拥有所有数字的进位时，退出外部循环.

Idea is the following: index your numbers from right to left (thus the reversed call in there). Increment the righternmost digit. As long as you hit the limit of n there, reset to zero but increment the digit one further left. This is essentially adding 1 using long addition with carry. Exit the inner loop when there is no more carry. Exit the outer loop when you don't explicitly exit the inner one, i.e. when you have a carry for all digits.

在 https://ideone.com/n0ScW8 上运行测试.

实际上，现在我再次查看代码，我看到了一种使用单个循环的方法，并且避免了Python的for-else构造，该构造在某些其他语言中没有明显的对应关系.这次我们使用JavaScript进行更改.

Actually now that I look at the code again, I see a way to use a single loop, and avoid Python's for-else construct which has no obvious counterpart in some other languages. Let's use JavaScript this time, for a change.

a = Array.from(Array(n), x=>0);
i = n - 1;
while (i >= 0) {
  a[i]++;
  if (a[i] == n) {
    a[i] = 0;
    i--;
  } else {
    console.log(a.join(""));
    i = n - 1;
  }
}

请注意，两个版本都省略了初始的000…0解决方案，因此它们是一个简短的解决方案.容易在前面添加.还要注意，我读错了问题，所以我假设一个数字数组0到n-1，而实际上您是在问任意输入.但是一个简单的间接转换会变成另一个，因此我将其保留为练习.

Note that both versions omit the initial 000…0 solution, so they are short one solution. Easy to add that up front. Also notice that I misread the question, so I'm assuming an array of numbers 0 through n-1 while in fact you asked for arbitrary input. But a simple indirection will turn one into the other, so I leave that as an exercise.

这篇关于直角坐标系(一种特殊的直角坐标系产品)-以可重复的样式从数组中选择元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！