Java中的字符串排列（非递归） [英] String permutations in Java (non-recursive)

问题描述

我是一名10年级的高中生，试图解决Java上的数据结构和算法书中的一些问题。

I'm a high school student of grade 10 trying to work through some problems in a Data Structures and Algorithms book on Java.

其中一个问题是打印字符串的所有排列。

One of the questions is to print all permutations of a string.

class C14
{
public static void main(char a[])
{
    // char[] a = {'c','a','r','b','o','n'};
    int c=0,w=0;
    for(int q = 0;q<a.length;q++) 
    {
        for(int i=0;i<a.length;i++)
        {
            for(int j=1;j<a.length;j++)
            {
                for(int k=1;k<a.length-1;k++) 
                {
                    for(int z=0;z<a.length;z++)
                    {
                        System.out.print(a[z]);
                        c++;
                    }
                    w++;
                    System.out.println();
                    char p=a[k+1];
                    a[k+1]=a[k];
                    a[k]=p;
                }
                System.out.println();
            }
            System.out.println();
            char x=a[0];
            a[0]=a[1];
            a[1]=x;
        }
      }
    System.out.println(" Character count = " + c);
    System.out.println(" Word count = " + w);
    }
}

这是我的尝试。这本书要求我为人物'c'，'a'，'r'，'b'，'o'，'n'做这件事。
我的解决方案正是如此，但当我尝试使用3或4个字母的单词时，它会让我重复。如果我删除最外面的循环并尝试打印它，它适用于3个和4个字母的单词，但不适用于5个以上的字母单词。

This is my attempt. The book asks me to do it for the characters 'c','a','r','b','o','n'. My solution does just that, but when I try to use 3 or 4 letter words, it gives me repetitions. If I remove the outermost loop and try to print it, it works for 3 and 4 letter words but not for 5+ letter words.

我很乐意澄清我的理由是，我知道这不是最有效率的，但请记住，我只是在10年级，这是我首先想到的。

I'll be glad to clarify my reasoning for it, I know it's not the most efficient, but do bear in mind the fact that I'm only in grade 10 and this is what came to my mind first.

有人可以帮助我，或至少暗示什么是错的？
请不要建议递归解决方案，因为我想先迭代地完成它。
谢谢，
Sumit。

Can someone please help me out, or at least hint at what's wrong? Please don't advise a recursive solution, because I want to work through it iteratively first. Thanks, Sumit.

推荐答案

重复排列

当你有n个东西可供选择时...你每次都有n个选择！

When you have n things to choose from ... you have n choices each time!

当选择其中的r时，排列是：

When choosing r of them, the permutations are:

n×n×...（r次）= n ^ r

n × n × ... (r times) = n^r

我提出2个案例。第一种情况是我们已经知道n和r的大小，而且很容易。第二个是n和r是动态的。

I'm presenting 2 cases. First case is when the we know the size of n and r already, and its the easy one. The second when n and r are dynamic.

//when n and r are known statically

class Permutation
{
    public static void main(String[] args)
    {
        char[] values = {'a', 'b', 'c', 'd'};
        int n = values.length;
        int r = 2; 

        int i = 0, j = 0;
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                System.out.println(values[j] + " " + values[i]);
            }
        }
    }
}


//when n and r are known only dynamically

class Permutation
{
    public static void main(String[] args)
    {
        char[] values = {'a', 'b', 'c', 'd'};
        int n = values.length;
        int r = 2; 
        int i[] = new int[r];
        int rc = 0;
        for(int j=0; j<Math.pow(n,r); j++)
        {

            rc=0;
            while(rc<r)
            {
                System.out.print(values[i[rc]] + " ");
                rc++;
            }
            System.out.println();
            rc = 0;
            while(rc<r)
            {
                if(i[rc]<n-1)
                {
                    i[rc]++;
                    break;
                }
                else
                {
                    i[rc]=0;
                }
                rc++;
            }
        }
    }
}

这篇关于Java中的字符串排列（非递归）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！