java - 如何限制排列的生成？ ( java 语)

Question

Dataset:
P1: Lion, Snow, Chair
P2: Min: 0, Max: 28
P3: Min: 34, Max is 39.

我的程序 以一系列数组列表的形式提供上述数据集(P1、P2、P3)。由此，它不断输出序列的不同变体，包括每个部分(P1、P2、P3)的一个元素，直到生成所有可能的排列。 (生成时P2和P3可以是它们各自的Min和Max之间的任意数字。)

这些序列的示例:

[Lion, 2, 37]
[Lion, 3, 34]
[Lion, 3, 35]
[Chair, 15, 35]
[Chair, 15, 36]
[Chair, 15, 37]
[Snow, 25, 36]
[Snow, 25, 37]
[Snow, 26, 34]

怎么做？

• 为此，我对 P1 使用了 getCombinations 函数，P2 和 P3 作为参数。准备 P2 和 P3 arraylists使用，我使用 fillArrayList 函数，它从最小填充到最大填充，然后返回相关的数组列表。
• 我面临的问题是，我对如何限制可能导致“不良结果”的排列输出感到困惑(迷失)，如下所示:

例如

• P1 = Lion && P2 > 23 && P3 <= 35 然后是糟糕的结果。
• P1 = Lion && P2 < 13 && P3 >= 37 然后是糟糕的结果。
• P1 = Chair && P2 < 7 && P3 = 34 结果不好。

虽然我愿意为每个条件语句静态编码一系列条件语句，但由于这些步骤是从一个可以更改的文件中读取的，所以这种方法不适用。

代码:

static ArrayList<ArrayList<String>> dataset = new ArrayList<ArrayList<String>>();
    static ArrayList<ArrayList<String>> rows = new ArrayList<ArrayList<String>>();
    static ArrayList<String> NegativePredictions = new ArrayList<String>();

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        init();

        for (ArrayList<String> curArrayList : dataset) {
            ArrayList<String> currentRule = new ArrayList<String>();
            if (curArrayList.size() > 2) {
                currentRule = curArrayList;

            } else {
                currentRule = new ArrayList<String>(
                        fillArrayList(Integer.parseInt(curArrayList.get(0)), Integer.parseInt(curArrayList.get(1))));

            }

            rows.add(currentRule);
        }
        getCombinations(rows).forEach(System.out::println);
    }

    public static void init() throws IOException {
        ArrayList<String> P1 = new ArrayList<String>(Arrays.asList("Lion", "Snow", "Chair"));
        ArrayList<String> P2 = new ArrayList<String>(Arrays.asList("0", "28"));
        ArrayList<String> P3 = new ArrayList<String>(Arrays.asList("34", "37"));

        dataset = new ArrayList<ArrayList<String>>(Arrays.asList(P1, P2, P3));

        NegativePredictions = new ArrayList<String>(Files.readAllLines(Paths.get("Predict.txt")));

    }

    public static ArrayList<String> fillArrayList(Integer start, Integer end) {

        ArrayList<String> returnedList = new ArrayList<String>();

        for (int i = start; i <= end; i++) {
            returnedList.add(String.valueOf(i));
        }
        return returnedList;
    }

    @SuppressWarnings("unchecked")
    public static <T> List<List<T>> getCombinations(Collection<? extends Iterable<T>> valueSetCollection) {
        Iterable<T>[] valueSets = new Iterable[valueSetCollection.size()];
        Iterator<T>[] valueIters = new Iterator[valueSetCollection.size()];
        T[] values = (T[]) new Object[valueSetCollection.size()];
        int i = 0;
        for (Iterable<T> valueSet : valueSetCollection) {
            valueSets[i] = valueSet; // Copy to array for fast index lookup
            valueIters[i] = valueSet.iterator();
            values[i] = valueIters[i].next(); // Fail if a wordSet is empty
            i++;
        }
        List<List<T>> combinations = new ArrayList<>();
        NEXT_COMBO: for (;;) {
            combinations.add(Arrays.asList(values.clone()));
            for (i = values.length - 1; i >= 0; i--) {
                if (valueIters[i].hasNext()) {
                    values[i] = valueIters[i].next();
                    continue NEXT_COMBO;
                }
                valueIters[i] = valueSets[i].iterator();
                values[i] = valueIters[i].next();
            }
            return combinations;
        }
    }
}

您会推荐什么？

Answer 1

考虑对规则进行编码，其中一组规则确定是否包含或排除特定的候选排列。比如定义一个规则的接口(interface):

    public interface ExclusionRule<X> {
        public boolean isExcluded(X x);
    }

以及几个知道如何与字符串或整数进行比较的实现:

    public class ExcludeIfEqualStringRule implements ExclusionRule<String> {
        private final String exclusion;

        public ExcludeIfEqualStringRule(String exclusion) {
            this.exclusion = exclusion;
        }

        @Override
        public boolean isExcluded(String x) {
            return x.equals(exclusion);
        }
    }

    public abstract class AbstractExcludeIntegerRule implements ExclusionRule<Integer> {
        private final int threshold;
        private final ExclusionRule<Integer> or;

        public AbstractExcludeIntegerRule(int threshold, ExclusionRule<Integer> or) {
            this.threshold = threshold;
            this.or = or;
        }

        @Override
        public final boolean isExcluded(Integer x) {
            if (or != null) {
                return or.isExcluded(x) || doComparison(x, threshold);
            }

            return doComparison(x, threshold);
        }

        protected abstract boolean doComparison(int x, int threshold);
    }

    public class ExcludeIfGreaterThanIntegerRule extends AbstractExcludeIntegerRule {

        public ExcludeIfGreaterThanIntegerRule(int threshold, ExclusionRule<Integer> or) {
            super(threshold, or);
        }

        public ExcludeIfGreaterThanIntegerRule(int threshold) {
            this(threshold, null);
        }

        @Override
        protected boolean doComparison(int x, int threshold) {
            return x > threshold;
        }
    }

    public class ExcludeIfLessThanIntegerRule extends AbstractExcludeIntegerRule {

        public ExcludeIfLessThanIntegerRule(int threshold, ExclusionRule<Integer> or) {
            super(threshold, or);
        }

        public ExcludeIfLessThanIntegerRule(int threshold) {
            this(threshold, null);
        }

        @Override
        protected boolean doComparison(int x, int threshold) {
            return x < threshold;
        }
    }

    public class ExcludeIfEqualIntegerRule extends AbstractExcludeIntegerRule {

        public ExcludeIfEqualIntegerRule(int threshold, ExclusionRule<Integer> or) {
            super(threshold, or);
        }

        public ExcludeIfEqualIntegerRule(int threshold) {
            this(threshold, null);
        }

        @Override
        protected boolean doComparison(int x, int threshold) {
            return x == threshold;
        }
    }

与另一个类一起定义了一组规则来评估任何候选排列:

    public class ExclusionEvaluator<T, U, V> {
        private final ExclusionRule<T> tRule;
        private final ExclusionRule<U> uRule;
        private final ExclusionRule<V> vRule;

        public ExclusionEvaluator(ExclusionRule<T> tRule, ExclusionRule<U> uRule, ExclusionRule<V> vRule) {
            this.tRule = tRule;
            this.uRule = uRule;
            this.vRule = vRule;
        }

        public boolean isExcluded(T t, U u, V v) {
            return tRule.isExcluded(t) && uRule.isExcluded(u) && vRule.isExcluded(v);
        }
    }

将三个列表作为单独的对象，可以将其封装在另一个提供 getCombinations() 方法的类中:

    public class PermutationProvider<T, U, V> {
        private final List<T> tItems;
        private final List<U> uItems;
        private final List<V> vItems;
        private final List<ExclusionEvaluator<T, U, V>> exclusionEvaluators;

        public PermutationProvider(List<T> tItems, List<U> uItems, List<V> vItems, List<ExclusionEvaluator<T, U, V>> exclusionEvaluators) {
            this.tItems = tItems;
            this.uItems = uItems;
            this.vItems = vItems;
            this.exclusionEvaluators = exclusionEvaluators;
        }

        public List<Permutation<T, U, V>> getCombinations() {
            List<Permutation<T, U, V>> combinations = new ArrayList<>();
            for (T tElement : tItems) {
                for (U uElement : uItems) {
                    for (V vElement : vItems) {
                        Permutation<T, U, V> p = new Permutation<>(tElement, uElement, vElement);
                        if (isExcluded(tElement, uElement, vElement)) {
                            System.out.println(p + " IS EXCLUDED");
                        } else {
                            combinations.add(p);
                        }
                    }
                }
            }

            return combinations;
        }

        private boolean isExcluded(T tElement, U uElement, V vElement) {
            for (ExclusionEvaluator<T, U, V> exclusionEvaluator : exclusionEvaluators) {
                if (exclusionEvaluator.isExcluded(tElement, uElement, vElement)) {
                    return true;
                }
            }

            return false;
        }
    }

和保存排列的结果类:

    public class Permutation<T, U, V> {
        private final T t;
        private final U u;
        private final V v;

        public Permutation(T t, U u, V v) {
            this.t = t;
            this.u = u;
            this.v = v;
        }

        public String toString() {
            return t.toString() + " " + u.toString() + " " + v.toString();
        }
    }

与驱动程序类一起构建列表、排除规则并获取可接受的排列:

public class PermuteWithExclusionsApp {

    public static void main(String[] args) {
        new PermuteWithExclusionsApp().permute();
    }

    private void permute() {
        List<String> p1 = Arrays.asList("Lion", "Chair", "Snow");

        List<Integer> p2 = new ArrayList<>();
        for (int i = 0; i <= 28; i++) {
            p2.add(i);
        }

        List<Integer> p3 = new ArrayList<>();
        for (int i = 34; i <= 39; i++) {
            p3.add(i);
        }

        // read from a file or some other source
        List<String> compoundExclusionRules = Arrays.asList("P1 = Lion && P2 > 23 && P3 <= 35", "P1 = Lion && P2 < 13 && P3 >= 37", "P1 = Chair && P2 < 7 && P3 = 34");

        ExclusionRuleFactory<String> stringRuleFactory = new StringExclusionRuleFactory();
        ExclusionRuleFactory<Integer> integerRuleFactory = new IntegerExclusionRuleFactory();
        ExclusionEvaluatorFactory<String, Integer, Integer> evaluatorFactory = new ExclusionEvaluatorFactory<>(stringRuleFactory, integerRuleFactory, integerRuleFactory);

        List<ExclusionEvaluator<String, Integer, Integer>> evaluators = new ArrayList<>();
        for (String compoundExclusionRule : compoundExclusionRules) {
            evaluators.add(evaluatorFactory.create(compoundExclusionRule));
        }

        //      List<ExclusionEvaluator<String, Integer, Integer>> evaluators = new ArrayList<>();
        //      evaluators.add(getExclusionRul1());
        //      evaluators.add(getExclusionRul2());
        //      evaluators.add(getExclusionRul3());

        PermutationProvider<String, Integer, Integer> provider = new PermutationProvider<>(p1, p2, p3, evaluators);
        List<Permutation<String, Integer, Integer>> permuations = provider.getCombinations();
        for (Permutation<String, Integer, Integer> p : permuations) {
            System.out.println(p);
        }
    }

    //  private ExclusionEvaluator<String, Integer, Integer> getExclusionRul3() {
    //      ExclusionRule<String> p1Rule = new ExcludeIfEqualStringRule("Chair");
    //      ExclusionRule<Integer> p2Rule = new ExcludeIfLessThanIntegerRule(7);
    //      ExclusionRule<Integer> p3Rule = new ExcludeIfEqualIntegerRule(34);
    //      return new ExclusionEvaluator<String, Integer, Integer>(p1Rule, p2Rule, p3Rule);
    //  }
    //
    //  private ExclusionEvaluator<String, Integer, Integer> getExclusionRul2() {
    //      ExclusionRule<String> p1Rule = new ExcludeIfEqualStringRule("Lion");
    //      ExclusionRule<Integer> p2Rule = new ExcludeIfLessThanIntegerRule(13);
    //      ExclusionRule<Integer> p3Rule = new ExcludeIfGreaterThanIntegerRule(37, new ExcludeIfEqualIntegerRule(37));
    //      return new ExclusionEvaluator<String, Integer, Integer>(p1Rule, p2Rule, p3Rule);
    //  }
    //
    //  private ExclusionEvaluator<String, Integer, Integer> getExclusionRul1() {
    //      ExclusionRule<String> p1Rule = new ExcludeIfEqualStringRule("Lion");
    //      ExclusionRule<Integer> p2Rule = new ExcludeIfGreaterThanIntegerRule(23);
    //      ExclusionRule<Integer> p3Rule = new ExcludeIfLessThanIntegerRule(35, new ExcludeIfEqualIntegerRule(35));
    //      return new ExclusionEvaluator<String, Integer, Integer>(p1Rule, p2Rule, p3Rule);
    //  }

这是一个工厂示例，如果规则被定义为文本，则可以解析排除规则。

    public interface ExclusionRuleFactory<Z> {
        public ExclusionRule<Z> create(String operator, String operand);
    }

    public class StringExclusionRuleFactory implements ExclusionRuleFactory<String> {

        @Override
        public ExclusionRule<String> create(String operator, String operand) {
            return new ExcludeIfEqualStringRule(operand);
        }
    }

    public class IntegerExclusionRuleFactory implements ExclusionRuleFactory<Integer> {

        @Override
        public ExclusionRule<Integer> create(String operator, String operand) {
            int threshold = Integer.parseInt(operand);

            switch (operator) {
            case "=":
                return new ExcludeIfEqualIntegerRule(threshold);

            case ">":
                return new ExcludeIfGreaterThanIntegerRule(threshold);

            case "<":
                return new ExcludeIfLessThanIntegerRule(threshold);

            case ">=":
                return new ExcludeIfGreaterThanIntegerRule(threshold, new ExcludeIfEqualIntegerRule(threshold));

            case "<=":
                return new ExcludeIfLessThanIntegerRule(threshold, new ExcludeIfEqualIntegerRule(threshold));
            }

            throw new IllegalArgumentException("Unsupported operator " + operator);
        }
    }

    public class ExclusionEvaluatorFactory<T, U, V> {
        private final ExclusionRuleFactory<T> p1RuleFactory;
        private final ExclusionRuleFactory<U> p2RuleFactory;
        private final ExclusionRuleFactory<V> p3RuleFactory;

        public ExclusionEvaluatorFactory(ExclusionRuleFactory<T> p1RuleFactory, ExclusionRuleFactory<U> p2RuleFactory, ExclusionRuleFactory<V> p3RuleFactory) {
            this.p1RuleFactory = p1RuleFactory;
            this.p2RuleFactory = p2RuleFactory;
            this.p3RuleFactory = p3RuleFactory;
        }

        public ExclusionEvaluator<T, U, V> create(String compoundExclusionRule) {
            ExclusionRule<T> p1Rule = null;
            ExclusionRule<U> p2Rule = null;
            ExclusionRule<V> p3Rule = null;

            String[] exclusionSubRules = compoundExclusionRule.split("&&");
            for (int sr = 0; sr < exclusionSubRules.length; sr++) {

                String[] ruleParts = exclusionSubRules[sr].trim().split(" ");
                String whichRule = ruleParts[0].trim(); 
                String operator = ruleParts[1].trim();
                String operand = ruleParts[2].trim();

                switch (whichRule) {
                case "P1":
                    p1Rule = p1RuleFactory.create(operator, operand);
                    break;

                case "P2":
                    p2Rule = p2RuleFactory.create(operator, operand);
                    break;

                case "P3":
                    p3Rule = p3RuleFactory.create(operator, operand);
                    break;
                }
            }

            return new ExclusionEvaluator<T, U, V>(p1Rule, p2Rule, p3Rule);
        }
    }