7

私は 10 年生の高校生で、Java に関するデータ構造とアルゴリズムの本でいくつかの問題を解決しようとしています。

問題の 1 つは、文字列のすべての順列を出力することです。

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 文字以上の単語では機能しません。

喜んでその理由を説明します。これが最も効率的ではないことは承知していますが、私はまだ 10 年生で、これが最初に頭に浮かんだという事実を覚えておいてください。

誰かが私を助けてくれますか、少なくとも何が問題なのかをほのめかすことはできますか? 最初に繰り返し処理したいので、再帰的な解決策をアドバイスしないでください。ありがとう、サミット。

4

1 に答える 1

3

繰り返しによる順列

n 個の選択肢がある場合、毎回 n 個の選択肢があります。

それらの r を選択すると、順列は次のようになります。

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

2事例紹介します。最初のケースは、n と r のサイズが既にわかっている場合で、簡単なケースです。n と r が動的な場合の 2 番目。

//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++;
            }
        }
    }
}
于 2012-08-30T06:38:42.817 に答える