توليد الاختلافات دون تكرار / التباديل في جافا

Question

لا بد لي من توليد جميع الاختلافات دون تكرار مصنوعة من الأرقام 0 - 9.

يمكن أن يكون طولها من 1 إلى 10. أنا حقا لا أعرف كيفية حلها، خاصة كيفية تجنب التكرار.

مثال: طول الاختلافات: 4 تباين عشوائي: 9856، 8753، 1243، 1234 إلخ (ولكن ليس 9985 - يحتوي على التكرار)

سأكون ممتنا حقا إذا كان بإمكان شخص ما مساعدتي في هذه المشكلة، خاصة إعطاء بعض الكود والأدائن.

Answer 1

الكلمة الرئيسية للبحث عن هي التقليب. وبعد هناك وفرة من التعليمات البرمجية المصدرية المتاحة بحرية التي تؤديها.

أما بالنسبة لإبقائه التكرار، أقترح اقتراح نهج متكرر بسيط: لكل رقم لديك خيار من أخذها في اختلافك أم لا، بحيث تحسب قواعدك من خلال الأرقام والشوك في مكالمتين متكررتان، يتم تضمين الرقم الذي يتم فيه تضمين الرقم ، واحد يتم فيه استبعادها. بعد ذلك، بعد أن وصلت إلى الرقم الأخير، تمنحك كل recursion أساسا قائمة (فريدة من نوعها، فرزها) بأرقام خالية من التكرار. يمكنك بعد ذلك إنشاء جميع التباديل الممكنة لهذه القائمة والجمع بين جميع هذه التبادلات لتحقيق النتيجة النهائية الخاصة بك.

(كما قال Duffymo: لن أؤكد رمز لذلك)

ملاحظة متقدمة: تعتمد العودية على 0/1 (الاستبعاد، الإدراج) والتي يمكن ترجمتها مباشرة إلى بت، وبالتالي، الأرقام الصحيحة. لذلك، من أجل الحصول على جميع المجموعات الرقمية الممكنة دون أداء العودية في الواقع، يمكنك ببساطة استخدام جميع الأرقام الصحيحة 10 بت وتكرر من خلالها. ثم قم بتفسير الأرقام بحيث يتوافق مجموعة المحددة بما في ذلك الرقم الموجود في القائمة التي يجب أن تصدر.

Answer 2

هنا هو رمز جافا الخاص بي. لا تتردد في طلب ما إذا كنت لا تفهم. النقطة الرئيسية هنا هي:

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");
    }
}

Answer 3

لقد قمت بإنشاء التعليمات البرمجية التالية لتوليد التباديل حيث الطلب مهم ومع عدم التكرار. إنه يستفيد من الأردن لاستبداد أي نوع من الكائن:

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;
    }
}

Answer 4

تخيل أن لديك وظيفة سحرية - بالنظر إلى مجموعة من الأرقام، ستعود لك التباديل الصحيح.

كيف يمكنك استخدام هذه الوظيفة لإنتاج قائمة جديدة من التباديل مع رقم واحد فقط؟

على سبيل المثال،

إذا أعطيتك وظيفة تسمى permute_three(char[3] digits), ، وأخبرك أنه يعمل فقط لأرقام 0, 1, 2, ، كيف يمكنك كتابة وظيفة يمكن أن تخلى 0, 1, 2, 3, ، باستخدام معين permute_three وظيفة؟

...

بمجرد حلها، ماذا تلاحظ؟ هل يمكنك تعميمها؟

Answer 5

استخدام دولار إنه بسيط:

@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));
    }
}

Answer 6

يشبه الكود الخاص بهذا واحد دون التكرارات، مع إضافة بيان IF-ENER.CHECK الشفرة

في التعليمات البرمجية أعلاه، قم بتحرير حلقة للنظام كما يلي

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;

}

عملت بالنسبة لي

Answer 7

يعتمد التقليب دون تكرار على نظرية، أن مقدار النتائج هو فعليا لعدد العناصر (في هذه الحالة). في قضيتك 10! هو 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. الدليل لماذا هو الصحيح تماما هو الحل الصحيح للجيل أيضا. حسنا، كيف. في المرتبة الأولى، أي من اليسار، يمكنك الحصول على 10 أرقام، في الموضع الثاني، يمكنك الحصول على 9 أرقام فقط، لأن رقم واحد موجود في الموضع على اليسار ولا يمكننا تكرار نفس الرقم وما إلى ذلك (يتم إجراء الدليل بواسطة التعريفي الرياضي ). فكيف تولد نتائج العشرة الأولى؟ وفقا لمعرفة بلدي، فإن أبسط طريقة هي استخدام التحول الدوري. هذا يعني ترتيب رقم التحول إلى اليسار في وضع واحد (أو صحيح إذا كنت تريد) والعدد الذي تجاوز لوضعه على المكان الفارغ. وهذا يعني أن النتائج العشرة الأولى:

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 7 6
...

السطر الأول هو عينة أساسية، لذلك فمن الجيد أن تضعها في تعيين قبل الجيل. ميزة، أنه في الخطوة التالية سيتعين عليك حل نفس المشكلة لتجنب التكرارات غير المرغوب فيها.

في الخطوة التالية تدوير بشكل متكرر فقط 10-1 الأرقام 10-1 مرات وما إلى ذلك. وهذا يعني لأول 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
...

إلخ، إشعار، أن السطر الأول موجود من الخطوة السابقة، لذلك يجب ألا تضاف إلى مجموعة تم إنشاؤها مرة أخرى.

خوارزمية لا تفعل ذلك تماما ذلك تماما، ما هو موضح أعلاه. من الممكن توليد جميع مجموعات 3628800 لمدة 10!، نظرا لأن عدد التعشيش هو نفس عدد العناصر الموجودة في الصفيف (يعني ذلك في قضيتك لمدة 10 أرقام، فإنها تصل إلى 5 دقائق. على جهاز الكمبيوتر الخاص بي) وتحتاج إلى ذاكرة كافية إذا كنت ترغب في الحفاظ على جميع المجموعات في الصفيف.

هناك حل.

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);
  }
}

شدة (عدد الدورات) من الخوارزمية هي مجموع الحقوق غير المكتملة لعدد الأعضاء. لذلك هناك overhang عندما تقرأ مجموعة جزئية مرة أخرى لتوليد مجموعة فرعية التالية، لذلك كثافة هي:

ن! + ن! / 2! + ن! / 3! + ... + N! / (N-2)! + ن! (n-1)!

Answer 8

هناك حل واحد الذي ليس من الألغام، لكنه لطيف للغاية ومتطور.

    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);
        }

    }
}

أعتقد أن هذا هو الحل الممتاز.

Answer 9

موجز المفيدة التخويل الفهرسة المعرفة

قم بإنشاء طريقة تنشئ التقليب الصحيح، بالنظر إلى قيمة فهرس بين {0 و n! -1} ل "صفر مفهرسة" أو {1 و n!} ل "مفهرسة واحدة".

قم بإنشاء طريقة ثانية تحتوي على "حلقة" حيث تكون الحد الأدنى هو 1 والحدود العلوي هو N! على سبيل المثال .. "ل (أنا؛ أنا <= n !؛ i ++)" لكل مثيل حلقة استدعاء الأسلوب الأول، يمر أنا كوسيطة.