#java #recursion #arraylist #dynamic-programming
Вопрос:
Мой код
public boolean canSplitArraySameAverage(ArrayList<Integer> a, ArrayList<Integer> b) {
double aSum = 0, bSum = 0;
for (int it : a) // aSum
aSum = aSum it;
for (int it : b) // bSum
bSum = bSum it;
if ((!a.isEmpty() amp;amp; !b.isEmpty()) amp;amp; (bSum / b.size() == aSum / a.size())) // Equal Average Possible
return true;
if (b.size() == 1) // Solution not possible, returning on reaching base case
return false;
for (int i = 0; i < b.size(); i ) {
a.add(b.remove(i)); // Transferring element from b to a
// Creating Deep Copies
ArrayList<Integer> newA = (ArrayList<Integer>) a.clone();
ArrayList<Integer> newB = (ArrayList<Integer>) b.clone();
if (canSplitArraySameAverage(newA, newB))
return true; // Early true return
}
System.out.println("Return :" a);
return false; // Solution not possible, returning after exhausting for loop
}
Логический поток о том, как должен выполняться код
Передача значений a[] и b[1 2 3 4]
При достижении отрицательного базового случая(размер b [] = 1) Я ожидаю, что значение a[] будет следующим
[1 2 3]
[1 2 4]
[1 2]
[1 3 2]
[1 3 4]
[1 3]
and so on
Однако мой код выполняется следующим образом
[1 2 3]
[1 2 4]
[1 3 2]
[1 3]
and terminates
Я не уверен, в чем проблема, я подозреваю, что это связано с операторами возврата.
Комментарии:
1. Вам действительно нужна петля for? Разве вы не можете просто использовать рекурсию, чтобы справиться с этим? Попробуйте удалить цикл и просто выполните одну передачу, если длина b > 1, и снова вызовите метод.
2. @nordenvall, я считаю, что цикл for необходим для того, чтобы ветвление происходило правильно, однако я могу ошибаться. Я попытался удалить цикл for и поместить в него код обновления, но затем он выполняет только самую левую ветвь. Результатом стало [1 2 3] [1 2] [1]
Ответ №1:
Перед клонированием списков массивов вы добавляете значение из исходного списка b в исходный список a .
Это означает, что при первом вызове вашего рекурсивного метода первый элемент исходного списка b (в вашем случае: 1) всегда будет первым элементом newA .
Решение этой проблемы заключается в переносе элемента после выполнения копирования:
// Creating Deep Copies
ArrayList<Integer> newA = (ArrayList<Integer>) a.clone();
ArrayList<Integer> newB = (ArrayList<Integer>) b.clone();
newA.add(newB.remove(i));
Примечание: Из-за вашего раннего истинного возвращения не все недействительные дела посещаются
Изменить: Дополнительные пояснения
Предполагая, что вы выполняете свой метод (из вопроса). Это не приведет ко всем возможным комбинациям и приведет к неправильному результату.
Причина, по которой не все комбинации проверяются, заключается в том, что вы переносите элементы из b в a , прежде чем делать копию.
Давайте посмотрим, что происходит в цикле for:
- Цикл for вводится с помощью
i == 0 - элемент передается из (оригинала)
bвa - теперь a = [1], b = [2,3,4]
- часть рекурсии происходит
- я увеличен. сейчас
i == 1 - поскольку вы удалили первый элемент из оригинала
b, следующий элемент, который будет добавлен, равен 3 (потомуi == 1что ) - это приводит к тому, что на следующем шаге комбинация [1,4] [2,3] никогда не рассматривается, и ваш метод дает неправильный результат.
Вот фиксированный код вашего метода:
public static boolean canSplitArraySameAverage(ArrayList<Integer> a, ArrayList<Integer> b) {
double aSum = a.stream().reduce(0, (x,y) -> x y);
double bSum = b.stream().reduce(0, (x,y) -> x y);
if ((!a.isEmpty() amp;amp; !b.isEmpty()) amp;amp; (bSum / b.size() == aSum / a.size())) // Equal Average Possible
return true;
if (b.size() == 1) // Solution not possible, returning on reaching base case
return false;
for (int i = 0; i < b.size(); i ) {
// Creating Deep Copies
ArrayList<Integer> newA = (ArrayList<Integer>) a.clone();
ArrayList<Integer> newB = (ArrayList<Integer>) b.clone();
// Transferring element from newB to newA
newA.add(newB.remove(i));
if (canSplitArraySameAverage(newA, newB))
return true; // Early true retur
}
System.out.println("Return :" a);
return false; // Solution not possible, returning after exhausting for loop
}
При выполнении этого метода с двумя списками a и b , где a пусто и b содержит [1,2,3,4] , вывод будет:
Return :[1, 2]
Return :[1, 3]
и результат метода «истинен», потому что разбиение на [1,4] и [2,3] дает одно и то же среднее значение.
Больше вывода нет, потому что, когда размер b равен 1, возвращается только значение false, без вывода.
Комбинации, проверенные на разных уровнях рекурсии, являются:
Recursion-Level: 0; a = [], b = [1, 2, 3, 4]
Recursion-Level: 1; a = [1], b = [2, 3, 4]
Recursion-Level: 2; a = [1, 2], b = [3, 4]
Recursion-Level: 3; a = [1, 2, 3], b = [4]
Recursion-Level: 3; a = [1, 2, 4], b = [3]
Recursion-Level: 2; a = [1, 3], b = [2, 4]
Recursion-Level: 3; a = [1, 3, 2], b = [4]
Recursion-Level: 3; a = [1, 3, 4], b = [2]
Recursion-Level: 2; a = [1, 4], b = [2, 3]
Комментарии:
1. В исходном вызове я передаю [ ] и [1 2 3 4] Во втором вызове он становится [1] и [2 3 4], Затем [1 2] и [3 4] И так далее, поэтому значение newA обновляется при каждом вызове, Если бы я печатал значения в ` b `перед обновлением и » a «после обновления, я получаю следующие значения» ‘B :[1 2 3 4] A :[1] B :[2 3 4] A :[1 2] B :[3 4] A :[1 2 3] B :[3 4] A :[1 2 3] B :[3 4] A :[1 2 4] B :[2 3 4] B :[3 4] A: [1 2 4] B: [2 3 4] А: [1 3] Б: [2 4] А: [1 3 2]»‘ Я также попробовал ваше предложение, оно дало мне [1 2 3 4] [1 2 3] [1 3] Не знаю, что с этим делать
2. @codingcredo Обновил мой ответ подробным объяснением, почему важно перенести элемент после клонирования списка. Если вам нужно напечатать больше проверяемых комбинаций, вам нужно добавить вывод к первому «возвращению false;» в вашем методе. Если вам нужно распечатать все комбинации, вам нужно переосмыслить свою стратегию раннего выхода.
3. большое вам спасибо! Сначала я неправильно понял ваше решение, и в итоге я дважды перенес элемент вместо изменения положения линии. И я также очень благодарен за подробное объяснение, которое помогло мне понять, где я ошибался и как вы это исправили!
Ответ №2:
Если вы хотите напечатать все невозможные значения, которые вы не можете вернуть из цикла for, вы выйдете из него при первой положительной комбинации.
Это работает для меня (извините, я переписал это на C#, так как у меня нет доступной среды разработки Java, но я думаю, вы понимаете изменения):
private bool CanSplitArraySameAverage(List<int> a, List<int> b)
{
double aSum = 0, bSum = 0;
foreach (var it in a)
{
aSum = aSum it;
}
foreach (int it in b)
{
bSum = bSum it;
}
if ((a.Any() amp;amp; b.Any()) amp;amp; (bSum / b.Count() == aSum / a.Count()))
{
return true;
}
bool canSplit = false;
if(b.Count() != 1)
{
for (int i = 0; i < b.Count(); i )
{
List<int> newA = new List<int>(a);
List<int> newB = new List<int>(b);
newA.Add(newB.ElementAt(i));
newB.RemoveAt(i);
if (this.CanSplitArraySameAverage(newA, newB))
{
canSplit = true;
}
}
}
if (!canSplit)
{
Console.WriteLine("Return :" String.Join("-", a));
}
return canSplit;
}
Дает результат:
Return :1-2-3
Return :1-2-4
Return :1-2
Return :1-3-2
Return :1-3-4
Return :1-3
Return :2-1-3
Return :2-1-4
Return :2-1
Return :2-4-1
Return :2-4-3
Return :2-4
Return :3-1-2
Return :3-1-4
Return :3-1
Return :3-4-1
Return :3-4-2
Return :3-4
Return :4-2-1
Return :4-2-3
Return :4-2
Return :4-3-1
Return :4-3-2
Return :4-3
Никаких комбинаций из 2-3 или 1-4
Комментарии:
1. Большое спасибо @nordenvall, это было полезно, и да, я смог следить за изменениями, спасибо!