如何进行 d-平滑序列算法
How to go about a d-smooth sequence algorithm
我真的很努力地设计一个算法来找到 d，它是可以添加或减去（最多）以使给定序列严格递增的最低值。
例如..说seq[] = [2,4,8,3,1,12]
给定该序列，算法应该 return“5”作为 d，因为您最多可以为每个元素加减 5，以便函数严格递增。
我尝试了几种方法，但似乎无法掌握可靠的技术。
我试过循环遍历 seq。并检查 seq[i] < seq[i+1]。如果不是，它检查是否 d>0.. 如果是，尝试从 seq[i+1] 中 add/subtract 它。否则它通过取 seq[i-1] - seq[i].
的差来计算 d
虽然我无法使其稳定，但它就像我一直在添加 if 语句，这些语句对于独特的输入序列来说更“特殊”。人们建议使用二进制搜索方法，但我无法将其应用于此问题。
非常感谢任何提示和建议。谢谢！
这是我正在编写的代码 - 使用 Python - v4
def ComputeMaxDelta3(seq):
# Create a copy to speed up comparison on modified values
aItems = seq[1:] #copies sequence elements from 1 (ignores seq[0])
# Will store the fix values for every item
# this should allocate 'length' times the 0 value
fixes = [0] * len(aItems)
print("fixes>>",fixes)
# Loop until no more fixes get applied
bNeedFix = True
while(bNeedFix):
# Hope will have no fix this turn
bNeedFix = False
# loop all subsequent item pairs (i should run from 0 to length - 2)
for i in range(0,len(aItems)-1):
# Left item
item1 = aItems[i]
# right item
item2 = aItems[i+1]
# Compute delta between left and right item
# We remember that (right >= left + 1
nDelta = item2 - (item1 + 1)
if(nDelta < 0):
# Fix the right item
fixes[i+1] -= nDelta
aItems[i+1] -= nDelta
# Need another loop
bNeedFix = True
# Compute the fix size (rounded up)
# max(s) should be int and the division should produce an int
nFix = int((max(fixes)+1)/2)
print("current nFix:",nFix)
# Balance all fixes
for i in range(len(aItems)):
fixes[i] -= nFix
print("final Fixes:",fixes)
print("d:",nFix)
print("original sequence:",seq[1:])
print("result sequence:",aItems)
return
显示的内容如下：
Working with: [6, 2, 4, 8, 3, 1, 12]
[0]= 6 So the following numbers are the sequence:
aItems = [2, 4, 8, 3, 1, 12]
fixes>> [0, 0, 0, 0, 0, 0]
current nFix: 6
final Fixes: [-6, -6, -6, 0, 3, -6]
d: 1
original sequence: [2, 4, 8, 3, 1, 12]
result sequence: [2, 4, 8, 9, 10, 12]
d SHOULD be: 5
done!
~注意~
我从 1 而不是 0 开始，因为第一个元素是键
这是我的解决方案：
public static int ComputeMaxDelta(int[] aItems, out int[] fixes)
{
// Create a copy to speed up comparison on modified values
aItems = (int[])aItems.Clone();
// Will store the fix values for every item
fixes = new int[aItems.Length];
// Loop until no more fixes get applied
var bNeedFix = true;
while (bNeedFix)
{
// Hope will have no fix this turn
bNeedFix = false;
// loop all subsequent item pairs
for (int ixItem = 0; ixItem < aItems.Length - 1; ixItem++)
{
// Left item
var item1 = aItems[ixItem];
// right item
var item2 = aItems[ixItem + 1];
// Compute delta between left and right item
// We remember that (right >= left + 1)
var nDelta = item2 - (item1 + 1);
if (nDelta < 0)
{
// Fix the right item
fixes[ixItem + 1] -= nDelta;
aItems[ixItem + 1] -= nDelta;
//Need another loop
bNeedFix = true;
}
}
}
// Compute the fix size (rounded up)
var nFix = (fixes.Max() + 1) / 2;
// Balance all fixes
for (int ixItem = 0; ixItem < aItems.Length; ixItem++)
fixes[ixItem] -= nFix;
return nFix;
}
函数returns计算出的最大修复间隙。
作为奖励，参数修复将收到每个项目的修复。这些是应用于每个源值的增量，以确保它们按升序排列：可以减少一些修复，但需要一些分析循环来实现该优化。
以下是算法测试代码。如果您在循环结束时设置断点，您将能够检查您在示例中提供的序列的结果。
var random = new Random((int)Stopwatch.GetTimestamp());
for (int ixLoop = -1; ixLoop < 100; ixLoop++)
{
int nCount;
int[] aItems;
// special case as the provided sample sequence
if (ixLoop == -1)
{
aItems = new[] { 2, 4, 8, 3, 1, 12 };
nCount = aItems.Length;
}
else
{
// Generates a random amount of items based on my screen's width
nCount = 4 + random.Next(21);
aItems = new int[nCount];
for (int ixItem = 0; ixItem < nCount; ixItem++)
{
// Keep the generated numbers below 30 for easier human analysis
aItems[ixItem] = random.Next(30);
}
}
Console.WriteLine("***");
Console.WriteLine(" # " + GetText(Enumerable.Range(0, nCount).ToArray()));
Console.WriteLine(" " + GetText(aItems));
int[] aFixes;
var nFix = ComputeMaxDelta(aItems, out aFixes);
// Computes the new values, that will be always in ascending order
var aNew = new int[aItems.Length];
for (int ixItem = 0; ixItem < aItems.Length; ixItem++)
{
aNew[ixItem] = aItems[ixItem] + aFixes[ixItem];
}
Console.WriteLine(" = " + nFix.ToString());
Console.WriteLine(" ! " + GetText(aFixes));
Console.WriteLine(" > " + GetText(aNew));
}
此致，
丹尼尔.
正如预期的那样，这是（或应该是）我最初解决方案的 Python 版本：
def ComputeMaxDelta(aItems):
# Create a copy to speed up comparison on modified values
aItems = aItems[:]
# Will store the fix values for every item
# this should allocate 'length' times the 0 value
fixes = [0] * len(aItems)
# Loop until no more fixes get applied
bNeedFix = True
while(bNeedFix):
# Hope will have no fix this turn
bNeedFix = False
# loop all subsequent item pairs (i should run from 0 to length - 2)
for i in range(0,len(aItems)-1):
# Left item
item1 = aItems[i]
# right item
item2 = aItems[i+1]
# Compute delta between left and right item
# We remember that (right >= left + 1
nDelta = item2 - (item1 + 1)
if(nDelta < 0):
# Fix the right item
fixes[i+1] -= nDelta
aItems[i+1] -= nDelta
# Need another loop
bNeedFix = True
# Compute the fix size (rounded up)
# max(s) should be int and the division should produce an int
nFix = (max(fixes)+1)/2 # corrected from **(max(s)+1)/2**
# Balance all fixes
for i in range(len(s)):
fixes[i] -= nFix
print("d:",nFix) # corrected from **print("d:",nDelta)**
print("s:",fixes)
return
我采用了您的 Python 并进行了修复，以便完全按照我的 C# 解决方案运行。
我不知道 Python，但在网上寻找一些参考资料，我应该找到你移植失败的地方。
如果将您的 python 版本与我的进行比较，您应该会发现以下差异：
- 您将引用 aItems 保存到 s 并将其用作我的 fixes，但是fixes 本来是从 0 开始的。
- 您没有在自身上克隆 aItems，然后对其项目的每个更改都反映在方法之外。
- 你的 for 循环从索引 1 开始，而我的循环从 0（第一个元素）开始。
- 检查 nDelta 后，您从 s 和 [=21] 中减去 nDelta =]aItems，但正如我在第 1 点和第 2 点所述，它们指向相同的项目。
- 不需要 ceil 指令，因为两个整数之间的除法产生一个整数，与 C# 一样。
请记住，我仅根据在线文档知识修复了 Python 代码，因为我不使用该语言编写代码，所以我不能 100% 确定某些语法（我的主要疑问关于 fixes 声明）。
此致，
丹尼尔.
我真的很努力地设计一个算法来找到 d，它是可以添加或减去（最多）以使给定序列严格递增的最低值。
例如..说seq[] = [2,4,8,3,1,12]
给定该序列，算法应该 return“5”作为 d，因为您最多可以为每个元素加减 5，以便函数严格递增。
我尝试了几种方法，但似乎无法掌握可靠的技术。
我试过循环遍历 seq。并检查 seq[i] < seq[i+1]。如果不是，它检查是否 d>0.. 如果是，尝试从 seq[i+1] 中 add/subtract 它。否则它通过取 seq[i-1] - seq[i].
的差来计算 d虽然我无法使其稳定，但它就像我一直在添加 if 语句，这些语句对于独特的输入序列来说更“特殊”。人们建议使用二进制搜索方法，但我无法将其应用于此问题。
非常感谢任何提示和建议。谢谢！
这是我正在编写的代码 - 使用 Python - v4
def ComputeMaxDelta3(seq):
# Create a copy to speed up comparison on modified values
aItems = seq[1:] #copies sequence elements from 1 (ignores seq[0])
# Will store the fix values for every item
# this should allocate 'length' times the 0 value
fixes = [0] * len(aItems)
print("fixes>>",fixes)
# Loop until no more fixes get applied
bNeedFix = True
while(bNeedFix):
# Hope will have no fix this turn
bNeedFix = False
# loop all subsequent item pairs (i should run from 0 to length - 2)
for i in range(0,len(aItems)-1):
# Left item
item1 = aItems[i]
# right item
item2 = aItems[i+1]
# Compute delta between left and right item
# We remember that (right >= left + 1
nDelta = item2 - (item1 + 1)
if(nDelta < 0):
# Fix the right item
fixes[i+1] -= nDelta
aItems[i+1] -= nDelta
# Need another loop
bNeedFix = True
# Compute the fix size (rounded up)
# max(s) should be int and the division should produce an int
nFix = int((max(fixes)+1)/2)
print("current nFix:",nFix)
# Balance all fixes
for i in range(len(aItems)):
fixes[i] -= nFix
print("final Fixes:",fixes)
print("d:",nFix)
print("original sequence:",seq[1:])
print("result sequence:",aItems)
return
显示的内容如下：
Working with: [6, 2, 4, 8, 3, 1, 12]
[0]= 6 So the following numbers are the sequence:
aItems = [2, 4, 8, 3, 1, 12]
fixes>> [0, 0, 0, 0, 0, 0]
current nFix: 6
final Fixes: [-6, -6, -6, 0, 3, -6]
d: 1
original sequence: [2, 4, 8, 3, 1, 12]
result sequence: [2, 4, 8, 9, 10, 12]
d SHOULD be: 5
done!
~注意~
我从 1 而不是 0 开始，因为第一个元素是键
这是我的解决方案：
public static int ComputeMaxDelta(int[] aItems, out int[] fixes)
{
// Create a copy to speed up comparison on modified values
aItems = (int[])aItems.Clone();
// Will store the fix values for every item
fixes = new int[aItems.Length];
// Loop until no more fixes get applied
var bNeedFix = true;
while (bNeedFix)
{
// Hope will have no fix this turn
bNeedFix = false;
// loop all subsequent item pairs
for (int ixItem = 0; ixItem < aItems.Length - 1; ixItem++)
{
// Left item
var item1 = aItems[ixItem];
// right item
var item2 = aItems[ixItem + 1];
// Compute delta between left and right item
// We remember that (right >= left + 1)
var nDelta = item2 - (item1 + 1);
if (nDelta < 0)
{
// Fix the right item
fixes[ixItem + 1] -= nDelta;
aItems[ixItem + 1] -= nDelta;
//Need another loop
bNeedFix = true;
}
}
}
// Compute the fix size (rounded up)
var nFix = (fixes.Max() + 1) / 2;
// Balance all fixes
for (int ixItem = 0; ixItem < aItems.Length; ixItem++)
fixes[ixItem] -= nFix;
return nFix;
}
函数returns计算出的最大修复间隙。 作为奖励，参数修复将收到每个项目的修复。这些是应用于每个源值的增量，以确保它们按升序排列：可以减少一些修复，但需要一些分析循环来实现该优化。
以下是算法测试代码。如果您在循环结束时设置断点，您将能够检查您在示例中提供的序列的结果。
var random = new Random((int)Stopwatch.GetTimestamp());
for (int ixLoop = -1; ixLoop < 100; ixLoop++)
{
int nCount;
int[] aItems;
// special case as the provided sample sequence
if (ixLoop == -1)
{
aItems = new[] { 2, 4, 8, 3, 1, 12 };
nCount = aItems.Length;
}
else
{
// Generates a random amount of items based on my screen's width
nCount = 4 + random.Next(21);
aItems = new int[nCount];
for (int ixItem = 0; ixItem < nCount; ixItem++)
{
// Keep the generated numbers below 30 for easier human analysis
aItems[ixItem] = random.Next(30);
}
}
Console.WriteLine("***");
Console.WriteLine(" # " + GetText(Enumerable.Range(0, nCount).ToArray()));
Console.WriteLine(" " + GetText(aItems));
int[] aFixes;
var nFix = ComputeMaxDelta(aItems, out aFixes);
// Computes the new values, that will be always in ascending order
var aNew = new int[aItems.Length];
for (int ixItem = 0; ixItem < aItems.Length; ixItem++)
{
aNew[ixItem] = aItems[ixItem] + aFixes[ixItem];
}
Console.WriteLine(" = " + nFix.ToString());
Console.WriteLine(" ! " + GetText(aFixes));
Console.WriteLine(" > " + GetText(aNew));
}
此致，
丹尼尔.
正如预期的那样，这是（或应该是）我最初解决方案的 Python 版本：
def ComputeMaxDelta(aItems):
# Create a copy to speed up comparison on modified values
aItems = aItems[:]
# Will store the fix values for every item
# this should allocate 'length' times the 0 value
fixes = [0] * len(aItems)
# Loop until no more fixes get applied
bNeedFix = True
while(bNeedFix):
# Hope will have no fix this turn
bNeedFix = False
# loop all subsequent item pairs (i should run from 0 to length - 2)
for i in range(0,len(aItems)-1):
# Left item
item1 = aItems[i]
# right item
item2 = aItems[i+1]
# Compute delta between left and right item
# We remember that (right >= left + 1
nDelta = item2 - (item1 + 1)
if(nDelta < 0):
# Fix the right item
fixes[i+1] -= nDelta
aItems[i+1] -= nDelta
# Need another loop
bNeedFix = True
# Compute the fix size (rounded up)
# max(s) should be int and the division should produce an int
nFix = (max(fixes)+1)/2 # corrected from **(max(s)+1)/2**
# Balance all fixes
for i in range(len(s)):
fixes[i] -= nFix
print("d:",nFix) # corrected from **print("d:",nDelta)**
print("s:",fixes)
return
我采用了您的 Python 并进行了修复，以便完全按照我的 C# 解决方案运行。 我不知道 Python，但在网上寻找一些参考资料，我应该找到你移植失败的地方。
如果将您的 python 版本与我的进行比较，您应该会发现以下差异：
- 您将引用 aItems 保存到 s 并将其用作我的 fixes，但是fixes 本来是从 0 开始的。
- 您没有在自身上克隆 aItems，然后对其项目的每个更改都反映在方法之外。
- 你的 for 循环从索引 1 开始，而我的循环从 0（第一个元素）开始。
- 检查 nDelta 后，您从 s 和 [=21] 中减去 nDelta =]aItems，但正如我在第 1 点和第 2 点所述，它们指向相同的项目。
- 不需要 ceil 指令，因为两个整数之间的除法产生一个整数，与 C# 一样。
请记住，我仅根据在线文档知识修复了 Python 代码，因为我不使用该语言编写代码，所以我不能 100% 确定某些语法（我的主要疑问关于 fixes 声明）。
此致，
丹尼尔.