原文:
给定两个整数 k 和 n，编写一个函数，打印由数字 1，2 组成的所有长度为 k 的序列..你需要按排序顺序打印这些序列。 例:
input: k = 2, n = 3
output:
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
input: k = 3, n = 4
output:
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
.....
.....
4 3 4
4 4 1
4 4 2
4 4 3
4 4 4
方法 1(简单且迭代): 按排序顺序打印所有序列的简单思路是从{1 1 … 1}开始，并在序列没有变成{n n … n}时不断递增序列。下面是详细的过程。 1)创建大小为 k 的输出数组 arr[]。将数组初始化为{1，1…1}。 2)打印数组 arr[]。 3)更新 arr[]数组，使其成为自身的直接后继(待打印)。例如，{1，1，1}的直接继任者是{1，1，2}，{1，4，4}的直接继任者是{2，1，1}，{4，4，3}的直接继任者是{4 4 4}。 4)当有后续阵列时，重复步骤 2 和 3。换句话说，虽然输出数组 arr[]没有变成{n，n..n} 现在我们来谈谈如何修改数组，使其包含直接后继。根据定义，直接后继应该有相同的第一个 p 项和更大的第(p l)项。在原始数组中，(p 1)第项(或 arr[p])小于 n，arr[p]之后的所有项，即 arr[p 1]、arr[p 2]、… arr[k-1]都是 n. 为了找到直接的后继项，我们在之前打印的数组中找到点 p。为了找到点 p，我们从最右边开始，一直移动，直到找到一个数字 arr[p]，使得 arr[p]小于 n(或者不是 n)。一旦我们找到这样一个点，我们将它递增 arr[p]1，并使 arr[p]之后的所有元素都为 1，也就是说，我们确实 arr[p 1] = 1，arr[p 2] = 1..arr[k-1] = 1。以下是获取 arr[]的直接后继者的详细步骤: 1)从最右边的术语 arr[k-1]开始，向左移动。找到与 n 不相同的第一个元素 arr[p]。 2)将 arr[p]增加 1 3)从 arr[p 1]开始到 arr[k-1]，将所有项的值设置为 1。
c
// cpp program of above approach
#include
using namespace std;
/* a utility function that prints a given arr[] of length size*/
void printarray(int arr[], int size)
{
for(int i = 0; i < size; i )
cout <<" "<< arr[i];
cout <<"\n";
return;
}
/* this function returns 0 if there are no more sequences to be printed, otherwise
modifies arr[] so that arr[] contains next sequence to be printed */
int getsuccessor(int arr[], int k, int n)
{
/* start from the rightmost side and find the first number less than n */
int p = k - 1;
while (arr[p] == n)
p--;
/* if all numbers are n in the array then there is no successor, return 0 */
if (p < 0)
return 0;
/* update arr[] so that it contains successor */
arr[p] = arr[p] 1;
for(int i = p 1; i < k; i )
arr[i] = 1;
return 1;
}
/* the main function that prints all sequences from 1, 1, ..1 to n, n, ..n */
void printsequences(int n, int k)
{
int *arr = new int[k];
/* initialize the current sequence as the first sequence to be printed */
for(int i = 0; i < k; i )
arr[i] = 1;
/* the loop breaks when there are no more successors to be printed */
while(1)
{
/* print the current sequence */
printarray(arr, k);
/* update arr[] so that it contains next sequence to be printed. and if
there are no more sequences then break the loop */
if(getsuccessor(arr, k, n) == 0)
break;
}
delete(arr); // free dynamically allocated array
return;
}
/* driver program to test above functions */
int main()
{
int n = 3;
int k = 2;
printsequences(n, k);
return 0;
}
// this code is contributed by shivanisinghss2110
c
// cpp program of above approach
#include
/* a utility function that prints a given arr[] of length size*/
void printarray(int arr[], int size)
{
for(int i = 0; i < size; i )
printf("%d ", arr[i]);
printf("\n");
return;
}
/* this function returns 0 if there are no more sequences to be printed, otherwise
modifies arr[] so that arr[] contains next sequence to be printed */
int getsuccessor(int arr[], int k, int n)
{
/* start from the rightmost side and find the first number less than n */
int p = k - 1;
while (arr[p] == n)
p--;
/* if all numbers are n in the array then there is no successor, return 0 */
if (p < 0)
return 0;
/* update arr[] so that it contains successor */
arr[p] = arr[p] 1;
for(int i = p 1; i < k; i )
arr[i] = 1;
return 1;
}
/* the main function that prints all sequences from 1, 1, ..1 to n, n, ..n */
void printsequences(int n, int k)
{
int *arr = new int[k];
/* initialize the current sequence as the first sequence to be printed */
for(int i = 0; i < k; i )
arr[i] = 1;
/* the loop breaks when there are no more successors to be printed */
while(1)
{
/* print the current sequence */
printarray(arr, k);
/* update arr[] so that it contains next sequence to be printed. and if
there are no more sequences then break the loop */
if(getsuccessor(arr, k, n) == 0)
break;
}
delete(arr); // free dynamically allocated array
return;
}
/* driver program to test above functions */
int main()
{
int n = 3;
int k = 2;
printsequences(n, k);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program of above approach
class gfg
{
/* a utility function that prints a given arr[] of length size*/
static void printarray(int arr[], int size)
{
for (int i = 0; i < size; i )
{
system.out.printf("%d ", arr[i]);
}
system.out.printf("\n");
return;
}
/* this function returns 0 if there are
no more sequences to be printed, otherwise
modifies arr[] so that arr[] contains
next sequence to be printed */
static int getsuccessor(int arr[], int k, int n)
{
/* start from the rightmost side and
find the first number less than n */
int p = k - 1;
while (arr[p] == n)
{
p--;
if (p < 0)
{
break;
}
}
/* if all numbers are n in the array
then there is no successor, return 0 */
if (p < 0)
{
return 0;
}
/* update arr[] so that it contains successor */
arr[p] = arr[p] 1;
for (int i = p 1; i < k; i )
{
arr[i] = 1;
}
return 1;
}
/* the main function that prints all
sequences from 1, 1, ..1 to n, n, ..n */
static void printsequences(int n, int k)
{
int[] arr = new int[k];
/* initialize the current sequence as
the first sequence to be printed */
for (int i = 0; i < k; i )
{
arr[i] = 1;
}
/* the loop breaks when there are
no more successors to be printed */
while (true)
{
/* print the current sequence */
printarray(arr, k);
/* update arr[] so that it contains
next sequence to be printed. and if
there are no more sequences then
break the loop */
if (getsuccessor(arr, k, n) == 0)
{
break;
}
}
}
/* driver code */
public static void main(string[] args)
{
int n = 3;
int k = 2;
printsequences(n, k);
}
}
// this code is contributed by princiraj1992
python 3
# python3 program of above approach
# a utility function that prints
# a given arr[] of length size#
def printarray(arr, size):
for i in range(size):
print(arr[i], end = " ")
print()
return
# this function returns 0 if there are
# no more sequences to be printed, otherwise
# modifies arr[] so that arr[] contains
# next sequence to be printed #
def getsuccessor(arr, k, n):
# start from the rightmost side and
# find the first number less than n
p = k - 1
while (arr[p] == n and 0 <= p < k):
p -= 1
# if all numbers are n in the array
# then there is no successor, return 0
if (p < 0):
return 0
# update arr[] so that it contains successor
arr[p] = arr[p] 1
i = p 1
while(i < k):
arr[i] = 1
i = 1
return 1
# the main function that prints all sequences
# from 1, 1, ..1 to n, n, ..n
def printsequences(n, k):
arr = [0] * k
# initialize the current sequence as
# the first sequence to be printed #
for i in range(k):
arr[i] = 1
# the loop breaks when there are
# no more successors to be printed
while(1):
# print the current sequence
printarray(arr, k)
# update arr[] so that it contains
# next sequence to be printed. and if
# there are no more sequences then
# break the loop
if(getsuccessor(arr, k, n) == 0):
break
return
# driver code
n = 3
k = 2
printsequences(n, k)
# this code is contributed by shubhamsingh10
c
// c# program of above approach
using system;
class gfg
{
/* a utility function that prints
a given []arr of length size*/
static void printarray(int []arr, int size)
{
for (int i = 0; i < size; i )
{
console.write("{0} ", arr[i]);
}
console.write("\n");
return;
}
/* this function returns 0 if there are
no more sequences to be printed, otherwise
modifies []arr so that []arr contains
next sequence to be printed */
static int getsuccessor(int []arr, int k, int n)
{
/* start from the rightmost side and
find the first number less than n */
int p = k - 1;
while (arr[p] == n)
{
p--;
if (p < 0)
{
break;
}
}
/* if all numbers are n in the array
then there is no successor, return 0 */
if (p < 0)
{
return 0;
}
/* update []arr so that it contains successor */
arr[p] = arr[p] 1;
for (int i = p 1; i < k; i )
{
arr[i] = 1;
}
return 1;
}
/* the main function that prints all
sequences from 1, 1, ..1 to n, n, ..n */
static void printsequences(int n, int k)
{
int[] arr = new int[k];
/* initialize the current sequence as
the first sequence to be printed */
for (int i = 0; i < k; i )
{
arr[i] = 1;
}
/* the loop breaks when there are
no more successors to be printed */
while (true)
{
/* print the current sequence */
printarray(arr, k);
/* update []arr so that it contains
next sequence to be printed. and if
there are no more sequences then
break the loop */
if (getsuccessor(arr, k, n) == 0)
{
break;
}
}
}
/* driver code */
public static void main(string[] args)
{
int n = 3;
int k = 2;
printsequences(n, k);
}
}
// this code is contributed by rajput-ji
java 描述语言
输出:
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
时间复杂度:总共有 n^k 序列。打印一个序列并找到它的后继序列需要很长时间。所以上述实现的时间复杂度是 o(k*n^k).
辅助空间: o(k) 方法 2(棘手且递归) 递归函数print sequence recurse生成并打印长度为 k 的所有序列，其思想是多使用一个参数索引。函数打印顺序递归将 arr[]中的所有项保持在正常状态，直到索引，更新索引处的值，并在索引后递归调用自身以获取更多项。
c
// c program of above approach
#include
using namespace std;
/* a utility function that prints a given arr[] of length size*/
void printarray(int arr[], int size)
{
for(int i = 0; i < size; i )
cout<< " "<< arr[i];
cout<<"\n";
return;
}
/* the core function that recursively generates and prints all sequences of
length k */
void printsequencesrecur(int arr[], int n, int k, int index)
{
int i;
if (k == 0)
{
printarray(arr, index);
}
if (k > 0)
{
for(i = 1; i<=n; i)
{
arr[index] = i;
printsequencesrecur(arr, n, k-1, index 1);
}
}
}
/* a function that uses printsequencesrecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printsequences(int n, int k)
{
int *arr = new int[k];
printsequencesrecur(arr, n, k, 0);
delete(arr); // free dynamically allocated array
return;
}
/* driver program to test above functions */
int main()
{
int n = 3;
int k = 2;
printsequences(n, k);
return 0;
}
// this code is contributed by shivanisinghss2110
c
// c program of above approach
#include
/* a utility function that prints a given arr[] of length size*/
void printarray(int arr[], int size)
{
for(int i = 0; i < size; i )
printf("%d ", arr[i]);
printf("\n");
return;
}
/* the core function that recursively generates and prints all sequences of
length k */
void printsequencesrecur(int arr[], int n, int k, int index)
{
int i;
if (k == 0)
{
printarray(arr, index);
}
if (k > 0)
{
for(i = 1; i<=n; i)
{
arr[index] = i;
printsequencesrecur(arr, n, k-1, index 1);
}
}
}
/* a function that uses printsequencesrecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printsequences(int n, int k)
{
int *arr = new int[k];
printsequencesrecur(arr, n, k, 0);
delete(arr); // free dynamically allocated array
return;
}
/* driver program to test above functions */
int main()
{
int n = 3;
int k = 2;
printsequences(n, k);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program of above approach
class gfg {
/* a utility function that prints a given arr[] of length size*/
static void printarray(int arr[], int size)
{
for(int i = 0; i < size; i )
system.out.print(arr[i] " ");
system.out.println();
return;
}
/* the core function that recursively generates and prints all sequences of
length k */
static void printsequencesrecur(int arr[], int n, int k, int index)
{
int i;
if (k == 0)
{
printarray(arr, index);
}
if (k > 0)
{
for(i = 1; i<=n; i)
{
arr[index] = i;
printsequencesrecur(arr, n, k-1, index 1);
}
}
}
/* a function that uses printsequencesrecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
static void printsequences(int n, int k)
{
int arr[] = new int[k];
printsequencesrecur(arr, n, k, 0);
return ;
}
/* driver program to test above functions */
public static void main(string[] args)
{
int n = 3;
int k = 2;
printsequences(n, k);
}
}
python 3
# python3 program of above approach
# a utility function that prints a
# given arr[] of length size
def printarray(arr, size):
for i in range(size):
print(arr[i], end = " ");
print("");
return;
# the core function that recursively
# generates and prints all sequences
# of length k
def printsequencesrecur(arr, n, k, index):
if (k == 0):
printarray(arr, index);
if (k > 0):
for i in range(1, n 1):
arr[index] = i;
printsequencesrecur(arr, n, k - 1,
index 1);
# a function that uses printsequencesrecur() to
# prints all sequences from 1, 1, ..1 to n, n, ..n
def printsequences(n, k):
arr = [0] * n;
printsequencesrecur(arr, n, k, 0);
return;
# driver code
n = 3;
k = 2;
printsequences(n, k);
# this code is contributed mits
c
// c# program of above approach
using system;
class gfg
{
/* a utility function that prints a given
arr[] of length size*/
static void printarray(int []arr, int size)
{
for(int i = 0; i < size; i )
console.write(arr[i] " ");
console.writeline();
return;
}
/* the core function that recursively generates
and prints all sequences of length k */
static void printsequencesrecur(int []arr, int n,
int k, int index)
{
int i;
if (k == 0)
{
printarray(arr, index);
}
if (k > 0)
{
for(i = 1; i<=n; i)
{
arr[index] = i;
printsequencesrecur(arr, n, k - 1, index 1);
}
}
}
/* a function that uses printsequencesrecur() to
prints all sequences from 1, 1, ..1 to n, n, ..n */
static void printsequences(int n, int k)
{
int[] arr = new int[k];
printsequencesrecur(arr, n, k, 0);
return;
}
// driver code
public static void main()
{
int n = 3;
int k = 2;
printsequences(n, k);
}
}
// this code is contributed
// by akanksha rai
服务器端编程语言（professional hypertext preprocessor 的缩写）
0)
{
for($i = 1; $i <= $n; $i)
{
$arr[$index] = $i;
printsequencesrecur($arr, $n,
$k - 1, $index 1);
}
}
}
/* a function that uses printsequencesrecur() to
prints all sequences from 1, 1, ..1 to n, n, ..n */
function printsequences($n, $k)
{
$arr = array();
printsequencesrecur($arr, $n, $k, 0);
return;
}
// driver code
$n = 3;
$k = 2;
printsequences($n, $k);
// this code is contributed
// by akanksha rai
?>
java 描述语言
输出:
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
时间复杂度:有 n^k 序列，打印一个序列需要 o(k)个时间。所以时间复杂性就是 o(k*n^k).
辅助空间: o(k) 感谢莫普赛勇士提示上述方法。正如 alphayoung** 所建议的，我们可以避免对能够适合一个整数的小序列使用数组。以下是相同的实现。
c
// c program of above approach
/* the core function that generates and
prints all sequences of length k */
void printseqrecur(int num, int pos, int k, int n)
{
if (pos == k)
{
cout << num << endl;
return;
}
for (int i = 1; i <= n; i )
{
printseqrecur(num * 10 i, pos 1, k, n);
}
}
/* a function that uses printsequencesrecur()
to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printsequences(int k, int n)
{
printseqrecur(0, 0, k, n);
}
// this code is contributed by shubhamsingh10
c
// c program of above approach
/* the core function that generates and prints all sequences of length k */
void printseqrecur(int num, int pos, int k, int n)
{
if (pos == k) {
printf("%d \n", num);
return;
}
for (int i = 1; i <= n; i ) {
printseqrecur(num * 10 i, pos 1, k, n);
}
}
/* a function that uses printsequencesrecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printsequences(int k, int n)
{
printseqrecur(0, 0, k, n);
}
java 语言(一种计算机语言，尤用于创建网站)
// java program of above approach
/* the core function that generates and prints all sequences of length k */
static void printseqrecur(int num, int pos, int k, int n)
{
if (pos == k) {
system.out.print(num " ");
return;
}
for (int i = 1; i <= n; i ) {
printseqrecur(num * 10 i, pos 1, k, n);
}
}
/* a function that uses printsequencesrecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
static void printsequences(int k, int n)
{
printseqrecur(0, 0, k, n);
}
python 3
# python program of above approach
# we have used number instead of
# arrays to prevent linear time
# required to print each string
def printseqrecur ( num , n, k ):
if n == 0: # if total digits become equal
# to n, print the number and return
print(num )
return
for _ in range(1, k 1):
printseqrecur (num * 10 _, n - 1, k)
# driver code
if __name__ == "__main__":
k = 3 # length of k-ary string
n = 2 # string can take values
# from 1,2,3...n
printseqrecur(0, n, k)
# this code is contributed
# by shivam purohit
c
// c# program of above approach
/* the core function that generates
and prints all sequences of length k */
static void printseqrecur(int num, int pos,
int k, int n)
{
if (pos == k)
{
console.write(num " ");
return;
}
for (int i = 1; i <= n; i )
{
printseqrecur(num * 10 i, pos 1, k, n);
}
}
/* a function that uses printsequencesrecur()
to prints all sequences from 1, 1, ..1 to n, n, ..n */
static void printsequences(int k, int n)
{
printseqrecur(0, 0, k, n);
}
// this code is contributed by code_mech
服务器端编程语言（professional hypertext preprocessor 的缩写）
java 描述语言
时间复杂度: o(kn^k)*
辅助空间: o(n * k)
参考文献: 的问题与pg电子试玩链接的解决方案如果您发现任何不正确的地方，或者您想分享更多关于上面讨论的主题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
