10

0〜9の数字を繰り返さずにすべてのバリエーションを生成する必要があります。

それらの長さは1から10までである可能性があります。私はそれを解決する方法、特に繰り返しを避ける方法を本当に知りません。

例：バリエーションの長さ：4つのランダムなバリエーション：9856、8753、1243、1234など（9985ではない-繰り返しを含む）

誰かがその問題について私を助けてくれたら、特にいくつかのコードと手がかりを与えてくれれば本当にありがたいです。

4

10 に答える 10

7

探すキーワードは順列です。それらを実行するために自由に利用できるソースコードが豊富にあります。

繰り返しのない状態を維持することに関しては、単純な再帰的アプローチを提案します。各桁について、バリエーションに取り込むかどうかを選択できるため、再帰は数字をカウントし、2つの再帰呼び出しに分岐します。1つには数字が含まれます。 、除外されているもの。次に、最後の桁に到達した後、各再帰は基本的に、繰り返しのない桁の（一意のソートされた）リストを提供します。次に、このリストのすべての可能な順列を作成し、それらの順列をすべて組み合わせて、最終結果を得ることができます。

（duffymoが言ったのと同じ：私はそのためのコードを提供しません）

高度な注意：再帰は0/1（除外、包含）に基づいており、ビット、つまり整数に直接変換できます。したがって、実際に再帰自体を実行せずにすべての可能な数字の組み合わせを取得するには、すべての10ビット整数を使用してそれらを反復処理するだけです。次に、セットビットが並べ替える必要のある数字をリストに含めることに対応するように数値を解釈します。

于 2009-12-14T11:04:29.027 に答える
4

これが私のJavaコードです。わからない場合はお気軽にお問い合わせください。ここでの主なポイントは次のとおりです。

  1. 文字配列を再度ソートします。例：a1 a2 a3 b1 b2 b3 ....（a1 = a2 = a3）
  2. 順列を生成し、常に条件を維持します：a1のインデックス<a2のインデックス<a3のインデックス..。
import java.util.Arrays;

public class PermutationDup {

    public void permutation(String s) {
        char[] original = s.toCharArray();
        Arrays.sort(original);
        char[] clone = new char[s.length()];
        boolean[] mark = new boolean[s.length()];
        Arrays.fill(mark, false);
        permute(original, clone, mark, 0, s.length());
    }

    private void permute(char[] original, char[] clone, boolean[] mark, int length, int n) {
        if (length == n) {
            System.out.println(clone);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (mark[i] == true) continue;
            // dont use this state. to keep order of duplicate character
            if (i > 0 && original[i] == original[i-1] && mark[i-1] == false) continue;
            mark[i] = true;
            clone[length] = original[i];
            permute(original, clone, mark, length+1, n);
            mark[i] = false;
        }

    }

    public static void main(String[] args) {
        PermutationDup p = new PermutationDup();
        p.permutation("abcab");
    }
}
于 2015-06-18T15:18:12.313 に答える
2

順序付けが重要で、繰り返しがない順列を生成するために、次のコードを作成しました。ジェネリックスを使用して、あらゆるタイプのオブジェクトを並べ替えます。

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations {

    public static <T> Collection<List<T>> generatePermutationsNoRepetition(Set<T> availableNumbers) {
        Collection<List<T>> permutations = new HashSet<>();

        for (T number : availableNumbers) {
            Set<T> numbers = new HashSet<>(availableNumbers);
            numbers.remove(number);

            if (!numbers.isEmpty()) {
                Collection<List<T>> childPermutations = generatePermutationsNoRepetition(numbers);
                for (List<T> childPermutation : childPermutations) {
                    List<T> permutation = new ArrayList<>();
                    permutation.add(number);
                    permutation.addAll(childPermutation);
                    permutations.add(permutation);
                }
            } else {
                List<T> permutation = new ArrayList<>();
                permutation.add(number);
                permutations.add(permutation);
            }
        }

        return permutations;
    }
}
于 2016-05-26T10:38:55.310 に答える
0

あなたが魔法の関数を持っていたと想像してください-数字の配列が与えられると、それはあなたに正しい順列を返します。

その関数を使用して、1桁余分に追加された順列の新しいリストを作成するにはどうすればよいですか？

例えば、

私があなたにと呼ばれる関数を与え、それが数字、、、に対してpermute_three(char[3] digits)のみ機能することをあなたに伝えた場合、与えられた関数を使用して、、、、を順列化できる関数をどのように書くことができますか？0120123permute_three

..。

それを解決したら、何に気づきますか？一般化できますか？

于 2009-12-14T13:29:30.187 に答える
0

ドルを使用するのは簡単です。

@Test
public void generatePermutations() {
    // digits is the string "0123456789"
    String digits = $('0', '9').join();

    // then generate 10 permutations
    for (int i : $(10)) {
        // shuffle, the cut (0, 4) in order to get a 4-char permutation
        System.out.println($(digits).shuffle().slice(4));
    }
}
于 2010-02-01T16:46:36.213 に答える
0

このコードは、重複のないコードと似ていますが、if-elseステートメントが追加されています。このコードを確認してください。

上記のコードで、forループを次のように編集します

for (j = i; j <= n; j++)
{

if(a[i]!=a[j] && !is_duplicate(a,i,j))              
    {
        swap((a+i), (a+j));
        permute(a, i+1, n);
        swap((a+i), (a+j)); 
    }
    else if(i!=j)  {}  // if no duplicate is present , do nothing           
    else permute(a,i+1,n);  // skip the ith character
}

bool is_duplicate(int *a,int i,int j) 
{
     if a[i] is present between a[j]...a[i] 
        return 1;
    otherwise
        return 0;

}

私のために働いた

于 2012-03-03T16:38:56.820 に答える
0

繰り返しのない順列は定理に基づいており、その結果の量は要素の数（この場合は数）の階乗です。あなたの場合は10！は10*9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800です。これが正確である理由の証明は、生成にも適切なソリューションです。さて、どうやって。最初の位置、つまり左から10個の数字、2番目の位置では9個の数字しか持てません。これは、1つの数字が左側の位置にあり、同じ数字を繰り返すことができないためです（数学的帰納法によって証明が行われます）。 ）。では、最初の10個の結果を生成する方法は？私の知識によれば、彼の最も簡単な方法は循環シフトを使用することです。これは、1つの位置で左（または必要に応じて右）にシフトする番号の順序と、空の場所に配置するためにオーバーフローする番号を意味します。これは、最初の10件の結果を意味します。

10 9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 1 10 9 8 7
5 4 3 2 1 10 9 8 76
..。

最初の行は基本的なサンプルなので、生成する前にセットに入れることをお勧めします。利点は、次のステップで、望ましくない重複を回避するために同じ問題を解決する必要があることです。

次のステップでは、10-1の数字だけを10-1回再帰的に回転させます。これは、ステップ2の最初の9つの結果を意味します。

10 9 8 7 6 5 4 3 2 1
10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 2 1 9 8 7 6
..。

など、前のステップの最初の行が存在するため、生成されたセットに再度追加してはならないことに注意してください。

上で説明したように、アルゴリズムはまさにそれを再帰的に実行します。ネストの数は配列内の要素の数と同じであり（つまり、10の数の場合、私のコンピューターでは約5分残ります）、十分なメモリが必要なため、10！のすべての3628800の組み合わせを生成できます。すべての組み合わせを配列に保持したい場合。

解決策があります。

package permutation;

/** Class for generation amount of combinations (factorial)
 * !!! this is generate proper permutations without repeating and proper amount (počet) of rows !!!
 *
 * @author hariprasad
 */
public class TestForPermutationII {
  private static final String BUMPER = "*";
  private static int counter = 0;
  private static int sumsum = 0;
  // definitoin of array for generation
  //int[] testsimple = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int[] testsimple = {1, 2, 3, 4, 5};
  private int ELEMNUM = testsimple.length;
  int[][] shuff;

  private String gaps(int len) {
    String addGap = "";
    for(int i=0; i <len; i++)
      addGap += "  ";
    return addGap;
  }

  /** Factorial computing */
  private int fact(int num) {
    if (num > 1) {
      return num * fact(num - 1);
    } else {
      return 1;
    }
  }

  /** Cyclic shift position to the left */  
  private int[] lShiftPos(int[] arr, int pos) {
    int[] work = new int[ELEMNUM];
    int offset = -1;
    for (int jj = 0; jj < arr.length; jj++) {
      if (jj < pos) {
        work[jj] = arr[jj];
      } else if (jj <= arr.length - 1) {
        if (jj == pos) {
          offset = arr[pos]; // last element
        }
        if (jj != (arr.length - 1)) {
          work[jj] = arr[jj + 1];
        } else {
          work[jj] = offset;
        }
      }
    }
    return work;
  }

  private String printBuff(int[] buffer) {
    String res = "";
    for (int i= 0; i < buffer.length; i++) {
      if (i == 0) 
        res += buffer[i];
      else
        res += ", " + buffer[i];
    }
    return res;
  };

  /** Recursive generator for arbitrary length of array */
  private String permutationGenerator(int pos, int level) {
    String ret = BUMPER;
    int templen = counter;
    int[] work = new int[ELEMNUM];
    int locsumread = 0;
    int locsumnew = 0;
    //System.out.println("\nCalled level: " + level);

    for (int i = 0; i <= templen; i++) {
      work = shuff[i];
      sumsum++;
      locsumread++;
      for (int ii = 0; ii < pos; ii++) {
        counter++;
        sumsum++;
        locsumnew++;
        work = lShiftPos(work, level); // deep copy
        shuff[counter] = work;
      }
    }

    System.out.println("locsumread, locsumnew: " + locsumread + ", " + locsumnew);
    // if level == ELEMNUM-2, it means no another shift
    if (level < ELEMNUM-2) {
      ret = permutationGenerator(pos-1, level+1);
      ret = "Level " + level + " end.";
      //System.out.println(ret);
    }
    return ret;
  }

  public static void main(String[] argv) {
    TestForPermutationII test = new TestForPermutationII();
    counter = 0;
    int len = test.testsimple.length;
    int[] work = new int[len];

    test.shuff = new int[test.fact(len)][];

    //initial
    test.shuff[counter] = test.testsimple;
    work = test.testsimple; // shalow copy

    test.shuff = new int[test.fact(len)][];
    counter = 0;
    test.shuff[counter] = test.testsimple;
    test.permutationGenerator(len-1, 0);

    for (int i = 0; i <= counter; i++) {
      System.out.println(test.printBuff(test.shuff[i]));
    }

    System.out.println("Counter, cycles: " + counter + ", " + sumsum);
  }
}

アルゴリズムの強度（サイクル数）は、メンバー数の不完全な階乗の合計です。したがって、次のサブセットを生成するために部分セットが再度読み取られるときにオーバーハングがあるため、強度は次のようになります。

n！+ n！/ 2！+ n！/ 3！+ ... + n！/（n-2）！+ n！（n-1）！

于 2015-09-15T10:54:12.507 に答える
0

私のものではない解決策が1つありますが、それは非常に素晴らしく洗練されています。

    package permutations;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * @author Vladimir Hajek
 *
 */
public class PermutationSimple {
    private static final int MAX_NUMBER = 3;

    Set<String> results = new HashSet<>(0);

    /**
     * 
     */
    public PermutationSimple() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param availableNumbers
     * @return
     */
    public static List<String> generatePermutations(Set<Integer> availableNumbers) {
        List<String> permutations = new LinkedList<>();

        for (Integer number : availableNumbers) {
            Set<Integer> numbers = new HashSet<>(availableNumbers);
            numbers.remove(number);

            if (!numbers.isEmpty()) {
                List<String> childPermutations = generatePermutations(numbers);
                for (String childPermutation : childPermutations) {
                    String permutation = number + childPermutation;
                    permutations.add(permutation);
                }
            } else {
                permutations.add(number.toString());
            }
        }

        return permutations;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Set<Integer> availableNumbers = new HashSet<>(0);

        for (int i = 1; i <= MAX_NUMBER; i++) {
            availableNumbers.add(i);
        }

        List<String> permutations = generatePermutations(availableNumbers);
        for (String permutation : permutations) {
            System.out.println(permutation);
        }

    }
}

これは優れたソリューションだと思います。

于 2015-10-17T20:22:39.070 に答える
0

簡単で役立つ順列索引付け知識

{0とNの間のインデックス値を指定して、正しい順列を生成するメソッドを作成します。-1}は「ゼロインデックス」の場合、または{1とN！}は「1インデックス」の場合。

下限が1で上限がN！である「forループ」を含む2番目のメソッドを作成します。例：ループのすべてのインスタンスに対して「for（i; i <= N !; i ++）」は、引数としてiを渡して、最初のメソッドを呼び出します。

于 2016-08-14T22:41:08.357 に答える
0 
def find(alphabet, alpha_current, str, str_current, max_length, acc):
  
  if (str_current == max_length):
    acc.append(''.join(str))
    return
  
  for i in range(alpha_current, len(alphabet)):
    str[str_current] = alphabet[i]
    
    alphabet[i], alphabet[alpha_current] = alphabet[alpha_current], alphabet[i]
    
    find(alphabet, alpha_current+1, str, str_current+1, max_length, acc)
    
    alphabet[i], alphabet[alpha_current] = alphabet[alpha_current], alphabet[i]
  
  return

max_length = 4
str = [' ' for i in range(max_length)]
acc = list()
find(list('absdef'), 0, str, 0, max_length, acc)

for i in range(len(acc)):
  print(acc[i])

print(len(acc))
于 2020-06-28T03:06:40.787 に答える