#c#
#c#
Вопрос:
Я хотел бы знать, как эффективно проверить, является ли массив int циклической перестановкой другого (или равен) в C #.
Например, следующие массивы являются циклическими перестановками: {1,2,3} , {2,3,1} и {3,1,2} , тогда как {2,1,3} это не так. Есть идеи?
Комментарии:
1. Могут ли числа дублироваться? То есть, что, если у нас есть
{1, 1, 2}и{1, 2, 1}, совпадает ли это?2. Я отмечаю, что обычно это называется циклической перестановкой , а не циклической перестановкой .
3. Вы запрашиваете эффективное решение, не говоря, что вы подразумеваете под «эффективным». Асимптотически эффективен? Возникает нехватка памяти? Быстро ли отбрасываются очевидные плохие совпадения? Каков ваш показатель эффективности?
4. Вы говорите, что у вас есть метод грубой силы, но вы не говорите, что это такое. Помогите нам помочь вам . Нам нет смысла повторять работу, которую вы уже выполнили и отвергли. Задайте более конкретный вопрос .
5. Существует две версии этой проблемы. Общая проблема заключается в том, что у вас есть множество пар массивов (a, b), (c, d), (e, f) и так далее, и вы хотите увидеть, какие пары обладают свойством, что (x, y) имеет x циклическую перестановку y или нет. Более конкретная проблема заключается в следующем: у вас есть определенный массив «a», и у вас есть целая куча массивов b, c, d, e, f, g, … и вы хотите знать, какие из b, c, d, e, f, g являются циклическими перестановками «a». Это не та же проблема! Могут существовать методы предварительной обработки «a», чтобы решение было более эффективным для каждого возможного случая.
Ответ №1:
Следующий метод должен обеспечить желаемое поведение:
bool IsCyclicPermutation(int[] a, int[] b) {
if (a == null || b == null || a.Length != b.Length) return false;
for (int i = 0; i < a.Length; i )
{
if (a[i] == b[0]) // Potential starting point of cycle found
{
bool isCyclic = true;
for (int j = 1; j < b.Length amp;amp; isCyclic; j )
{
if (a[(j i) % a.Length] != b[j]) isCyclic = false;
}
if (isCyclic) return true; // Cycle found
}
}
return false; // No cycles found
}
Редактировать
Если это тот случай, когда повторяющиеся числа отсутствуют, вы можете использовать модифицированный код, как показано ниже, для немного лучшей производительности:
bool IsCyclicPermutation(int[] a, int[] b) {
if (a == null || b == null || a.Length != b.Length) return false;
for (int i = 0; i < a.Length; i )
{
if (a[i] == b[0]) // Starting point of potential cycle found
{
bool isCyclic = true;
for (int j = 1; j < b.Length amp;amp; isCyclic; j )
{
if (a[(j i) % a.Length] != b[j]) isCyclic = false;
}
return isCyclic;
}
}
return false; // No cycles found
}
Были выполнены следующие тесты:
var arr1 = new int[] {1, 2, 3};
var arr2 = new int[] {2, 3, 1};
var arr3 = new int[] {3, 1, 2};
var arr4 = new int[] {2, 1, 3};
IsCyclicPermutation(arr1, arr1); // True
IsCyclicPermutation(arr1, arr2); // True
IsCyclicPermutation(arr1, arr3); // True
IsCyclicPermutation(arr2, arr1); // True
IsCyclicPermutation(arr2, arr2); // True
IsCyclicPermutation(arr2, arr3); // True
IsCyclicPermutation(arr3, arr1); // True
IsCyclicPermutation(arr3, arr2); // True
IsCyclicPermutation(arr3, arr3); // True
IsCyclicPermutation(arr4, arr1); // False
IsCyclicPermutation(arr4, arr2); // False
IsCyclicPermutation(arr4, arr3); // False
Что касается производительности, трудно сказать, не имея с чем ее сравнить, хотя я верю, что это O (n), где n — размер входных массивов.
Комментарии:
1. Спасибо, это было именно то, что мне было нужно
2. @Couroux взгляните на мою правку, чтобы найти улучшенную функцию, которая будет использоваться, когда массивы не содержат повторяющихся значений.
Ответ №2:
int[] array1 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] array2 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int tmp = array1[0];
int index = Array.IndexOf(array2, tmp);
int n = array1.Length;
for (int i = 1; i < n; i )
{
if (index i < array1.Length)
{
if (array1[i] != array2[index i])
{
Console.WriteLine("Arrays are not equal");
break;
}
}
else
{
if (array1[i] != array2[index i - n])
{
Console.WriteLine("Arrays are not equal");
break;
}
}
}
Я предполагаю, что длина массивов и их элементов одинакова. Приведенный выше код выполняет работу в O (n). Дважды проверьте индекс!
Ответ №3:
Конечно:
using System;
using System.Linq;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
var test1 = new [] {1, 2, 3};
var test2 = new [] {2, 3, 1};
var test3 = new [] {3, 1, 2};
var test4 = new [] {2, 1, 3};
test1.IsCiruclarPermutation(test2);
test1.IsCiruclarPermutation(test3);
test2.IsCiruclarPermutation(test1);
test2.IsCiruclarPermutation(test3);
test3.IsCiruclarPermutation(test1);
test3.IsCiruclarPermutation(test2);
test4.IsCiruclarPermutation(test1);
test4.IsCiruclarPermutation(test2);
test4.IsCiruclarPermutation(test3);
}
}
public static class ArrayExtensions
{
public static bool IsCiruclarPermutation(this int[] source, int[] dest)
{
Console.Write(string.Join(",", source) " is a Ciruclar Permutation of ");
Console.Write(string.Join(",", dest));
var left = source.ToList();
var right = dest.ToList();
right.AddRange(dest);
var result = false;
for (int idx = 0; idx < left.Count; idx )
{
var compareTo = right.Skip(idx).Take(left.Count);
result = Enumerable.SequenceEqual(left, compareTo);
if (result) break;
}
Console.WriteLine(" " result.ToString());
return resu<
}
}
Вывод:
верно ли, что 1,2,3 — это циклическая перестановка 2,3,1
верно ли 1,2,3 — это циклическая перестановка 3,1,2
2,3,1 — верна ли циклическая перестановка 1,2,3
2,3,1 — верна ли циклическая перестановка 3,1,2
3,1,2 — верна ли циклическая перестановка 1,2,3
3,1,2 — верна ли циклическая перестановка 2,3,1
2,1,3 — это циклическая перестановка 1,2,3 False
2,1,3 — это циклическая перестановка 2,3,1 False
2,1,3 — это циклическая перестановка 3,1,2 False
Комментарии:
1. Вы говорите, что предстоит проделать работу по сравнению массивов разной длины. Можете ли вы привести пример двух массивов разной длины, где один является перестановкой другого?
2. Я отмечаю, что ни в одном из ваших тестовых примеров test1 не рассматривается как перестановка test1.
Ответ №4:
Если у вас сложная проблема, преобразуйте ее в simple problem, в следующем коде используйте linkedlist для решения проблемы, это не лучший вариант для производительности, но простой для понимания.
public class SameTest<T>
{
public bool TestCircularArray(IEnumerable<T> array1, IEnumerable<T> array2)
{
if (array1 == null)
throw new ArgumentNullException("array1");
if (array2 == null)
throw new ArgumentNullException("array2");
// if they are the same, the length must be the same
if (array1.Count() != array2.Count())
return false;
// two empty array assume to same
if (!array1.Any())
return true;
// convert array2 to linkedlist
var linkedList = new LinkedList<T>(array2);
LinkedListNode<T> node = null;
foreach (T item1 in array1)
{
// first find the element in link
if (node == null)
{
node = linkedList.Find(item1);
if (node == null)
return false;
continue;
}
node = node.Next;
// reach tail move to head
if (node == null)
node = linkedList.First;
if (!item1.Equals(node.Value))
return false;
}
return true;
}
}
[TestMethod]
public void TestMethod1()
{
int[] array1 = {2, 3, 1};
int[] array2 = {1, 2, 3};
int[] array3 = {2, 1, 3};
var tester = new SameTest<int>();
var result = tester.TestCircularArray(array1, array2);
Assert.AreEqual(true, result);
result = tester.TestCircularArray(array2, array3);
Assert.AreEqual(false, result);
}